danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"dan-327Research ArticleМАТЕМАТИКАMATHEMATICSРЕКУРСИВНОЕ ПРЕДСТАВЛЕНИЕ КЛАССА СЛОЖНОСТИ NP ∩ coNPRECURSIVE PRESENTATION OF THE COMPLEXITY CLASS NP∩coNPНАЙДЕНКОВ. Г.NAIDENKOV. G.vladimir.naidenko@gmail.comИнститут математики НАН БеларусиInstitute of Mathematics of the National Academy of Sciences of Belarus2016281020166043537Copyright © НАЙДЕНКО В.Г., 20162016НАЙДЕНКО В.Г.NAIDENKO V.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/327

Впервые получена рекурсивная представимость одного из базовых классов сложности NP ∩coNP с использованием полиномиальных недетерминированных машин Тьюринга.

Using nondeterministic polynomial time Turing machines, a recursive presentation of the complexity class NP ∩ coNP has been constructed for the first time.

вычислительная сложностьрекурсивная представимостьcomputational complexityrecursive presentationReferencesBrassard, G. A Note on Cryptography and NP ∩ CoNP–P / G. Brassard, S. Fortune, J. Hopcroft // Technical Report TR-338, Department of Computer Science, Cornell University. – Ithaca; N.Y., 1978.Brassard, G. A Note on Cryptography and NP ∩ CoNP–P / G. Brassard, S. Fortune, J. Hopcroft // Technical Report TR-338, Department of Computer Science, Cornell University. – Ithaca; N.Y., 1978.Kowalczyk, W. Some Connections between Representability of Complexity Classes and the Power of Formal Systems of Reasoning / W. Kowalczyk // Proceedings of the Mathematical Foundations of Computer Science. – 1984. – P. 364–369.Kowalczyk, W. Some Connections between Representability of Complexity Classes and the Power of Formal Systems of Reasoning / W. Kowalczyk // Proceedings of the Mathematical Foundations of Computer Science. – 1984. – P. 364–369.Dawar, A. On Complete Problems, Relativizations and Logics for Complexity Classes / A. Dawar // Lecture Notes in Computer Science. – 2010. – Vol. 6300. – P. 201–207.Dawar, A. On Complete Problems, Relativizations and Logics for Complexity Classes / A. Dawar // Lecture Notes in Computer Science. – 2010. – Vol. 6300. – P. 201–207.Papadimitriou, Ch. On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence / Ch. Papadimitriou // J. of Computer and System Sciences. – 1994. – Vol. 48, N 3. – P. 498–532.Papadimitriou, Ch. On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence / Ch. Papadimitriou // J. of Computer and System Sciences. – 1994. – Vol. 48, N 3. – P. 498–532.Naidenko, V. Logics for complexity classes / V. Naidenko // Logic J. of the IGPL. – 2014. – Vol. 22, N 6. – P. 1075–1093.Naidenko, V. Logics for complexity classes / V. Naidenko // Logic J. of the IGPL. – 2014. – Vol. 22, N 6. – P. 1075–1093.

The authors declare that there are no conflicts of interest present.