Solution of the Problem P = L

Sergey Goncharov and Andrey Nechesov
Additional contact information
Sergey Goncharov: Sobolev Institute of Mathematics, Academician Koptyug Ave., 4, 630090 Novosibirsk, Russia
Andrey Nechesov: Sobolev Institute of Mathematics, Academician Koptyug Ave., 4, 630090 Novosibirsk, Russia

Mathematics, 2021, vol. 10, issue 1, 1-8

Abstract: The problems associated with the construction of polynomial complexity computer programs require new techniques and approaches from mathematicians. One of such approaches is representing some class of polynomial algorithms as a certain class of special logical programs. Goncharov and Sviridenko described a logical programming language L 0 , where programs inductively are obtained from the set of Δ 0 -formulas using special terms. In their work, a new idea has been proposed to look at the term as a program. The computational complexity of such programs is polynomial. In the same years, a number of other logical languages with similar properties were created. However, the following question remained: can all polynomial algorithms be described in these languages? It is a long-standing problem, and the method of describing some polynomial algorithm in a not Turing complete logical programming language was not previously clear. In this paper, special types of terms and formulas have been found and added to solve this problem. One of the main contributions is the construction of p -iterative terms that simulate the work of the Turing machine. Using p -iterative terms, the work showed that class P is equal to class L , which extends the programming language L 0 with p -iterative terms. Thus, it is shown that L is quite expressive and has no halting problem, which occurs in high-level programming languages. For these reasons, the logical language L can be used to create fast and reliable programs. The main limitation of the language L is that the implementation of algorithms of complexity is not higher than polynomial.

Keywords: polynomiality; polynomial function; polynomial algorithm; Turing machine; logical programming language; semantic programming; smart contract; blockchain; AI (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/1/113/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/1/113/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2021:i:1:p:113-:d:715030

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().