|
Zapiski Nauchnykh Seminarov 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.
Received: 16.04.2012
Citation:
N. K. Kosovskiy, “Polynomial upper bounds of RAM+BOOL program size of changes for the proof of belonging to FP”, Studies in constructive mathematics and mathematical logic. Part XII, Zap. Nauchn. Sem. POMI, 407, POMI, St. Petersburg, 2012, 105–110; J. Math. Sci. (N. Y.), 199:1 (2014), 53–55
Linking options:
https://www.mathnet.ru/eng/znsl5487 https://www.mathnet.ru/eng/znsl/v407/p105
|
Statistics & downloads: |
Abstract page: | 232 | Full-text PDF : | 46 | References: | 42 |
|