Preview

Доклады Национальной академии наук Беларуси

Расширенный поиск

РЕКУРСИВНОЕ ПРЕДСТАВЛЕНИЕ КЛАССА СЛОЖНОСТИ NP ∩ coNP

Аннотация

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

Об авторе

В. Г. НАЙДЕНКО
Институт математики НАН Беларуси
Беларусь


Список литературы

1. 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.

2. 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.

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, N 3. – P. 498–532.

5. Naidenko, V. Logics for complexity classes / V. Naidenko // Logic J. of the IGPL. – 2014. – Vol. 22, N 6. – P. 1075–1093.


Рецензия

Просмотров: 639


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-8323 (Print)
ISSN 2524-2431 (Online)