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

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

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

Пример

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

Литература

• Кормен Т. Лейзерсон Ч. Ривест Р. . — Москва МЦНМО. от 21 августа 2019 на Wayback Machine