Email this article Logical Language of Description of Polynomial Computing
- Authors: Goncharov S.S.1, Sviridenko D.I.1
-
Affiliations:
- Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences
- Issue: Vol 99, No 2 (2019)
- Pages: 121-124
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225637
- DOI: https://doi.org/10.1134/S1064562419020030
- ID: 225637
Cite item
Open Access
Access granted
Subscription Access
Abstract
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.
About the authors
S. S. Goncharov
Sobolev Institute of Mathematics, Siberian Branch,Russian Academy of Sciences
Author for correspondence.
Email: s.s.goncharov@math.nsc.ru
Russian Federation, Novosibirsk, 630090
D. I. Sviridenko
Sobolev Institute of Mathematics, Siberian Branch,Russian Academy of Sciences
Author for correspondence.
Email: dsviridenko47@gmail.com
Russian Federation, Novosibirsk, 630090
Supplementary files
