Logical Language of Description of Polynomial Computing
Sergey Savostyanovich Goncharov, Д. И. Свириденко · Doklady Mathematics · 2019
The concept of a term and, accordingly, the concept of a formula are extended using new operators. These extensions of the language preserve the expressiveness of $$\Sigma $$ -formulas and, at the level of $${{\Delta }_{0}}$$ -formulas and terms, they ensure the polynomiality of algorithms for calculating the value of a term and deciding the truth of a $${{\Sigma }_{0}}$$ -formula.