informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-75Research ArticleСТАТЬИ ПО МАТЕРИАЛАМ КОНФЕРЕНЦИЙARTICLES ON THE MATERIALS CONFERENCEАЛГОРИТМИЧЕСКОЕ ПЕРЕЧИСЛЕНИЕ ЗАДАЧ В КЛАССЕ NPcoNPALGORITHMIC ENUMERATION OF PROBLEMS IN THE CLASS NPcoNPНайденкоВ. Г.NaidenkoV. G.vladimir.naidenko@gmail.comИнститут математики НАН БеларусиBelarus20160110201603101104Copyright © Найденко В.Г., 20162016Найденко В.Г.Naidenko V.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/75

Рассматривается проблема рекурсивного (алгоритмического) представления класса сложности NPcoNP. Предлагается новый метод алгоритмического перечисления всех задач в классе сложности NPcoNP с использованием полиномиальных недетерминированных машин Тьюринга.

The problem of recursive (algorithmic) representation is considered for the complexity class NPcoNP. A new method is proposed for algorithmically enumerating all problems in NPcoNP, using polynomial-time nondeterministic Turing machines.

ReferencesBrassard, G. A Note on Cryptography and NPCoNP–P / G. Brassard, S. Fortune, J. Hopcroft // Technical Report TR-338, Department of Computer Science. – Ithaca, N.Y. : Cornell University, 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. – Ithaca, N.Y. : Cornell University, 1978.Kowalczyk, W. Some Connections between Representability of Complexity Classes and the Power of Formal Systems of Reasoning / W. Kowalczyk // Proc. of the Mathematical Foundations of Computer Science. – Heidelberg : Springer, 1984. – Vol. 176. – P. 364–369.Kowalczyk, W. Some Connections between Representability of Complexity Classes and the Power of Formal Systems of Reasoning / W. Kowalczyk // Proc. of the Mathematical Foundations of Computer Science. – Heidelberg : Springer, 1984. – Vol. 176. – 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, no. 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, no. 3. – P. 498–532.Naidenko, V. Logics for complexity classes / V. Naidenko // Logic J. of the IGPL. – 2014. – Vol. 22, no. 6. – P. 1075–1093.Naidenko, V. Logics for complexity classes / V. Naidenko // Logic J. of the IGPL. – 2014. – Vol. 22, no. 6. – P. 1075–1093.

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