RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2012 Volume 407, Pages 105–110 (Mi znsl5487)

Polynomial upper bounds of RAM+BOOL program size of changes for the proof of belonging to FP

N. K. Kosovskiy

Saint-Petersburg State University, Saint-Petersburg, Russia

Abstract: 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.

Key words and phrases: RAM, Turing macine, function-oracle Turing macine, class FP.

UDC: 510.52

Received: 16.04.2012


 English version:
Journal of Mathematical Sciences (New York), 2014, 199:1, 53–55

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025