Polynomial upper bounds of RAM+BOOL program size of changes for the proof of belonging to~{\bf FP}

N. K. Kosovskiy

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XII, Tome 407 (2012), pp. 105-110

Résumé

RAM+BOOL (i.e. a random access machine with the additional bitwise logical operations) seams to be suitable enough mathematical notion of an algorithm for a more adequate (according to the computer operations) simulation of the number of computational steps than the notion of Turing machine. For example, the definition of RAM+BOOL contains indirect address widely used while array processing in computer. The RAM+BOOL used memory size (with logarithmical weight) is maximum over steps of a RAM+BOOL program run of the summs of the lengths of all values of all cells. The introduced by the author notion of the size of changes (which is a production of the number of steps and the used memory size) is offered to use in order to guarantee the belonging of RAM+BOOL computations to the class FP (i.e. to the class of all algorithms computable by a Turing machine in a polynomial time). Some statements concerning complexity characteristics of RAM+BOOL computations are proved in the paper. The most important of them is the following corollary. Corollary. The class of all RAM+BOOL programs, the size of chanches of which has a polynomial under the input data length upper bound, coincides with the class FP.