Класс 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-полной.

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

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

Пример

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

Литература

• Кормен Т. Лейзерсон Ч. Ривест Р. Алгоритмы : Построение и анализ: Учебник: пер. с англ.. — Москва МЦНМО. Архивная копия от 21 августа 2019 на Wayback Machine