Класс 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-полной задачи является проверка булевой формулы на тавтологичность. То есть, для всех ли наборов переменных данная формула истинна. Данная задача тесно связана с задачей выполнимости, в которой нужно узнать, существует ли хотя бы один такой набор переменных.
Литература править
- Кормен Т. Лейзерсон Ч. Ривест Р. Алгоритмы : Построение и анализ: Учебник: пер. с англ.. — Москва МЦНМО. Архивная копия от 21 августа 2019 на Wayback Machine