Язык \(L\) называется NP-полным, если выполняются два условия: \(L\in NP\) и любой язык \(K\in NP\) полиномиально сводится к
NP-полные задачи представляют наиболее трудную часть класса \(NP\) относительно полиномиальных сведений. Если хотя бы одна NP-полная задача принадлежит \(P\), то благодаря сводимости все задачи из \(NP\) принадлежат \(P\), то есть \(P=NP\)
Что важно запомнить
- NP-полнота требует одновременно \(L\in NP\) и сводимости к \(L\) всех задач из
- NP-полная задача является NP-трудной относительно выбранной полиномиальной сводимости.
- Если хотя бы одна NP-полная задача решается полиномиально, то \(P=NP\).
- Для новой задачи обычно доказывают принадлежность \(NP\) и сводят к ней уже известную NP-полную задачу.
Определение
NP-полный язык \(L\) удовлетворяет:
- \(L\in NP\).
- Для каждого \(K\in NP\) выполняется \(K\prec L\).
Второе условие означает, что алгоритм для \(L\) можно было бы использовать как универсальный полиномиальный подалгоритм для всех задач класса \(NP\), если добавить соответствующее
Главное следствие
Пусть \(L\) NP-полон и \(L\in P\). Для любого \(K\in NP\) имеем \(K\prec L\). Так как \(L\) решается детерминированно за полиномиальное время, по свойству сводимости \(K\in P\). Следовательно, \(NP\subseteq P\). Вместе с \(P\subseteq NP\) получаем
Как доказывают NP-полноту
После теоремы Кука—Левина нет необходимости каждый раз сводить к новой задаче все языки из \(NP\). Достаточно доказать, что новая задача принадлежит \(NP\), а затем полиномиально свести к ней уже известную NP-полную задачу. Транзитивность сводимости передаёт трудность всему классу.
Значение понятия
NP-полнота объединяет большое число внешне разных задач в один класс полиномиальной эквивалентности по трудности. Она показывает, что поиск полиномиального алгоритма для одной такой задачи связан с центральным вопросом о равенстве \(P\) и \(NP\). При этом само определение не утверждает, что полиномиального алгоритма не существует.
Пример простыми словами
Предположим, что SAT уже известна как NP-полная. Чтобы доказать NP-полноту новой задачи \(B\), сначала показывают \(B\in NP\). Затем строят сведение SAT \(\prec B\). После этого для любого \(K\in NP\) имеем \(K\prec SAT\prec B\), значит \(B\) NP-полна.
Частые ошибки
- Путать NP-полную и просто NP-трудную задачу. Для NP-полноты сама задача должна принадлежать \(NP\).
- Доказывать только \(B\prec SAT\). Такое направление показывает, что \(B\) не сложнее SAT, но не доказывает NP-трудность \(B\).
- Говорить, что NP-полные задачи «доказанно не имеют полиномиальных алгоритмов». Из определения этого не следует.
