Geodesic
Polynomial upper bounds of RAM+BOOL program size of changes for the proof of belonging to FP
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XII, Tome 407 (2012), pp. 105-110
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{ZNSL_2012_407_a4,
     author = {N. K. Kosovskiy},
     title = {Polynomial upper bounds of {RAM+BOOL} program size of changes for the proof of belonging {to~FP}},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {105--110},
     year = {2012},
     volume = {407},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_407_a4/}
}
TY  - JOUR
AU  - N. K. Kosovskiy
TI  - Polynomial upper bounds of RAM+BOOL program size of changes for the proof of belonging to FP
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 105
EP  - 110
VL  - 407
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_407_a4/
LA  - ru
ID  - ZNSL_2012_407_a4
ER  - 
%0 Journal Article
%A N. K. Kosovskiy
%T Polynomial upper bounds of RAM+BOOL program size of changes for the proof of belonging to FP
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 105-110
%V 407
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_407_a4/
%G ru
%F ZNSL_2012_407_a4
N. K. Kosovskiy. Polynomial upper bounds of RAM+BOOL program size of changes for the proof of belonging to FP. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XII, Tome 407 (2012), pp. 105-110. http://geodesic.mathdoc.fr/item/ZNSL_2012_407_a4/

[1] A. Akho, Dzh. Khopkroft, Dzh. Ulman, Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR

[2] N. K. Kosovskii, T. M. Kosovskaya, “Polinomialnost i NP-trudnost zadachi vychisleniya znaka postoyannogo terma”, Matematicheskie voprosy kibernetiki, 16, 2007, 125–128

[3] N. K. Kosovskii, “Usloviya polinomialnosti algoritmov, realizuemykh na mashinakh Tyuringa s orakulami-funktsiyami”, Materialy XVII Mezhdunarodnoi shkoly-seminara “Sintez i slozhnost upravlyayuschikh sistem” im. akad. O. B. Lupanova (Novosibirsk, 27 oktyabrya – 1 noyabrya 2008 g.), Izd-vo Instituta matematiki, Novosibirsk, 2008, 70–74

[4] S. A. Kuk, “Slozhnost protsedur vyvoda teorem”, Kib. sb., nov. ser., 12, 1975, 5–15

[5] D.-Z. Du, K.-I. Ko, Theory of Computational Complexity, A Wiley-Interscience Publication, John Wiley Sons, Inc., 2000 | MR