Zapiski Nauchnykh Seminarov POMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
References:
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
English version:
Journal of Mathematical Sciences (New York), 2014, Volume 199, Issue 1, Pages 53–55
DOI: https://doi.org/10.1007/s10958-014-1831-1
Bibliographic databases:
Document Type: Article
UDC: 510.52
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Kos12}
\by N.~K.~Kosovskiy
\paper Polynomial upper bounds of RAM+BOOL program size of changes for the proof of belonging to~{\bf FP}
\inbook Studies in constructive mathematics and mathematical logic. Part~XII
\serial Zap. Nauchn. Sem. POMI
\yr 2012
\vol 407
\pages 105--110
\publ POMI
\publaddr St.~Petersburg
\mathnet{http://mi.mathnet.ru/znsl5487}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3032185}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2014
\vol 199
\issue 1
\pages 53--55
\crossref{https://doi.org/10.1007/s10958-014-1831-1}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84902267460}
Linking options:
  • https://www.mathnet.ru/eng/znsl5487
  • https://www.mathnet.ru/eng/znsl/v407/p105
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:232
    Full-text PDF :46
    References:42
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024