Logical Language of Description of Polynomial Computing

Аннотация

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.