Класс Co-NP-complete

Co-NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет», принадлежащая классу co-NP, такая, что любая задача из этого класса может быть сведена к ней за полиномиальное время.

Если P ≠ co-NP, то никакая co-NP-полная задача не может быть решена за полиномиальное время. Если же какая-либо co-NP-полная задача может быть решена быстро, то быстрый алгоритм существует для любой задачи из класса co-NP.

Любая co-NP-полная задача является дополнением некоторой NP-полной задачи. Существуют задачи, которые принадлежат как классу NP, так и классу co-NP, например, любая задача из класса P и задача факторизации. При этом неизвестно, совпадают ли классы NP и co-NP или, что эквивалентно, существует ли задача, одновременно являющаяся NP- и co-NP-полной.

Формальное определение

Задача разрешимости является co-NP-полной, если она сама лежит в классе co-NP и любая другая задача из co-NP полиномиально сводится к ней. Другими словами, для любой задачи из класса co-NP существует алгоритм, который за полиномиальное время преобразует входные данные задачи во входные данные задачи таким образом, чтобы ответ к новой задаче совпадал с ответом исходной. Следовательно, если для задачи существует полиномиальный алгоритм, то любая задача из класса co-NP может быть решена за полиномиальное время.

Пример

Одним из простых примеров co-NP-полной задачи является проверка булевой формулы на тавтологичность. То есть, для всех ли наборов переменных данная формула истинна. Данная задача тесно связана с задачей выполнимости, в которой нужно узнать, существует ли хотя бы один такой набор переменных.

Литература
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.