Определение и смысл
- Решательская задача — множество входов, на которые ответ «да». Класс полиномиально разрешимых задач: $\mathrm{P}$.
- Класс $\mathrm{NP}$: задачи, для которых «да»-ответ можно проверить за полиномиальное время по некоторому свидетельству (сертификату).
- Явление NP‑полноты: задача $L$ называется NP‑полной, если
1) $L\in \mathrm{NP}$, и
2) любая задача $L^{\prime }\in \mathrm{NP}$ сводится к $L$ полиномиально (много‑в‑одно): существует функция $f$, вычислимая за полиномиальное время, такая что
$$x\in L^{\prime }⟺f(x)\in L.$$ Формально: $\forall L^{\prime }\in \mathrm{NP}(L^{\prime }{\le }_{p}L)$.
Важно: NP‑полнота — это признак вычислительной трудности (скорее всего отсутствие полиномиального алгоритма), а не неразрешимости; NP‑полная задача разрешима (по определению в $\mathrm{NP}$), просто неизвестно, существует ли для неё полиномиальный алгоритм (вопрос $\mathrm{P}=\mathrm{NP}?$).
Пример (стандартный)
- SAT: «существует ли булева формула, принимающая значение истина?» — это задача из $\mathrm{NP}$.
- Теорема Кука–Левина: SAT является NP‑полной.
- Часто используют вариант $\text{3-SAT}$: формула в CNF, каждая дизъюнкция содержит ровно 3 литерала; $\text{3-SAT}$ тоже NP‑полна.
Идея сводимости (наглядный пример)
- Пример сводимости $\text{3-SAT}{\le }_p\text{CLIQUE}$ (эскиз):
- Пусть формула имеет $m$ клауз (дизъюнктов). Построим граф так: для каждой клаузи и для каждого литерала в ней создаём вершину. Соединим ребром две вершины, если они принадлежат разным клаузам и соответствующие литералы не конфликтуют (не являются взаимно отрицательными). Тогда в графе существует клика размера $m$ тогда и только тогда, когда можно выбрать по одному литералу из каждой клаузи, совместные истиненны — т. е. формула выполнима. Порождаемую функцию преобразования можно вычислить за время полиномиальное от длины формулы.
- Это иллюстрирует типичный приём: показать, как любая «да»-сертификата из одной задачи превращается в «да»-сертификат другой через полиномиальную конструкцию.
Практические следствия для проектирования алгоритмов
- NP‑полнота означает вероятность отсутствия общего полиномиального алгоритма (если $\mathrm{P}\ne \mathrm{NP}$). На практике:
- Используют экспоненциальные, но оптимизированные алгоритмы (branch & bound, cut‑and‑branch, битовые методы). Часто работают для входов до сотен/тысяч элементов.
- Применяют эвристики и локальные поиски (GSAT, simulated annealing, greedy), хорошие в практике, но без гарантии оптимальности во всех случаях.
- Ищут приближённые алгоритмы с гарантиями (approximation algorithms) или доказывают невозможность близкой аппроксимации (hardness of approximation).
- Ограничивают класс входов: полиномиальные алгоритмы для специальных случаев (планарные графы, ограниченная степень, bounded treewidth и т. п.).
- Используют параметризированную сложность: фиксированный параметр $k$ и FPT‑алгоритмы с временем $f(k)\cdot n^{O(1)}$.
- Практически широко применяют мощные SAT/SMT/ILP‑солверы, которые решают реальные инстансы быстро, несмотря на теоретическую сложность.
- В криптографии опираются на предположения о трудности NP‑задач (или родственных задач), но аккуратно: безопасность обычно строится на более конкретных предположениях.
Кратко о границах теории
- NP‑полнота ≠ неразрешимость; NP‑полная задача разрешима, но, вероятно, не за полиномиальное время.
- Если когда‑то найдётся полиномиальный алгоритм для одной NP‑полной задачи, то для всех задач в $\mathrm{NP}$ будет полиномиальный алгоритм ($\mathrm{P}=\mathrm{NP}$).
Вывод: NP‑полнота формализует «самые трудные» задачи в $\mathrm{NP}$. Для практических систем это означает выбор стратегии: точные экспоненциальные методы, приближения, эвристики, ограничение входов или параметризация — в зависимости от требований к качеству решения и ресурсам.