×

zbMATH — the first resource for mathematics

Logical language of description of polynomial computing. (English. Russian original) Zbl 1432.03048
Dokl. Math. 99, No. 2, 121-124 (2019); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 485, No. 1, 11-14 (2019).
Summary: 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.
MSC:
03B70 Logic in computer science
03D15 Complexity of computation (including implicit computational complexity)
03B25 Decidability of theories and sets of sentences
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Goncharov, S. S.; Sviridenko, D. I., No article title, Vychisl. Sist., 107, 3-29, (1985)
[2] Goncharov, S. S.; Sviridenko, D. I., No article title, Lect. Notes Comput. Sci., 215, 169-179, (1986)
[3] Yu. L. Ershov, S. S. Goncharov, and D. I. Sviridenko, Information Processing 86: Proceedings of IFIP 10th World Computer Congress (Elsevier, Amsterdam, 1986), Vol. 10, pp. 1113-1120.
[4] Goncharov, S. S.; Sviridenko, D. I., No article title, Dokl. Akad. Nauk SSSR, 289, 1324-1328, (1986)
[5] Ershov, Yu. L.; Goncharov, S. S.; Sviridenko, D. I., No article title, Lect. Notes Comput. Sci., 278, 116-122, (1987)
[6] Ershov, Yu. L., No article title, Dokl. Akad. Nauk SSSR, 270, 786-788, (1983)
[7] Ershov, Yu. L., No article title, Dokl. Akad. Nauk SSSR, 273, 1045-1048, (1983)
[8] Yu. L. Ershov, Definability and Computability: Siberian School of Algebra and Logic (Consultants Bureau, New York, 1996).
[9] J. Barwise, Admissible Sets and Structures (Springer, Berlin, 1975). · Zbl 0316.02047
[10] S. Arora and B. Barak, Computational Complexity: A Modern Approach (Cambridge Univ. Press, Cambridge, 2009). · Zbl 1193.68112
[11] Ch. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, Mass., 1994). · Zbl 0833.68049
[12] Ospichev, S. S.; Ponomarev, D., No article title, Sib. Electron. Math. Rep., 15, 987-995, (2018)
[13] Goncharov, S. S., No article title, Sib. Math. J., 58, 794-800, (2017) · Zbl 1420.03059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.