АЛГОРИТМИЧЕСКОЕ ПЕРЕЧИСЛЕНИЕ ЗАДАЧ В КЛАССЕ NPcoNP
Аннотация
Рассматривается проблема рекурсивного (алгоритмического) представления класса сложности NPcoNP. Предлагается новый метод алгоритмического перечисления всех задач в классе сложности NPcoNP с использованием полиномиальных недетерминированных машин Тьюринга.
Список литературы
1. Brassard, G. A Note on Cryptography and NPCoNP-P / G. Brassard, S. Fortune, J. Hopcroft // Technical Report TR-338, Department of Computer Science. - Ithaca, N.Y. : Cornell University, 1978.
2. 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.
3. Dawar, A. On Complete Problems, Relativizations and Logics for Complexity Classes / A. Dawar // Lecture Notes in Computer Science. - 2010. - Vol. 6300. - P. 201-207.
4. 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.
5. Naidenko, V. Logics for complexity classes / V. Naidenko // Logic J. of the IGPL. - 2014. - Vol. 22, no. 6. - P. 1075-1093.
Для цитирования:
Найденко В.Г.
АЛГОРИТМИЧЕСКОЕ ПЕРЕЧИСЛЕНИЕ ЗАДАЧ В КЛАССЕ NPcoNP. Информатика. 2016;(3):101-104.
For citation:
Naidenko V.G.
ALGORITHMIC ENUMERATION OF PROBLEMS IN THE CLASS NPcoNP. Informatics. 2016;(3):101-104.
(In Russ.)
Просмотров: 829
Послать статью по эл. почте 