Кратко: NP-полнота — это свойство языков/задач: задача $L$ NP-полна, если
- $L\in$NP (решение можно проверить за полиномиальное время по сертификату), и
- для любой задачи $A\in$NP существует полиномиальная сводимость $f$ такая, что $x\in A⟺f(x)\in L$ (то есть $L$ NP-трудна).
Для оптимизационных задач обычно рассматривают их решение-версию (decision version): вместо «найти максимум» ставят вопрос «существует решение с качеством $\ge k$?\)». Демонстрация NP-полноты новой оптимизационной задачи проходит так:
Общий подход
- Формализовать decision-версию задачи: определить вход, параметр $k$ и требование «есть ли решение с ценностью $\ge k$?».
- Доказать, что задача принадлежит NP: показать, как по сертификату (напр., набор выбранных элементов) за полиномиальное время проверить, что значение $\ge k$.
- Выбрать известную NP-полную задачу $A$ (напр., $3$-SAT или INDEPENDENT SET).
- Построить полиномиальную функцию $f$, переводящую любую инстанцию $x$ задачи $A$ в инстанцию $f(x)$ вашей задачи так, чтобы $x$ позитивно тогда и только тогда, когда $f(x)$ позитивно. Доказать корректность и полиномиальность построения.
- Сделать вывод: поскольку $A$ сводится к вашей задаче, она NP-трудна; вместе с принадлежностью NP это даёт NP-полноту.
Конкретный пример: сведение $3$-SAT → INDEPENDENT SET (решение-версия Maximum Independent Set)
- Исходная задача: дана булева формула в CNF с $m$ клаузами $C_1,\dots ,C_m$, каждая клауза содержит не более трёх литералов. Нужно решить, выполнима ли формула.
- Целевая задача (решение): для графа $G$ и числа $k$ — существует ли независимое множество размера $\ge k$?
Построение графа $G$ из формулы $\varphi$:
- Для каждой клаузы $C_i$ создаём вершины, по одной на каждый литерал в клаузе. Если клауз имеет три литерала, делаем три вершины; между всеми вершинами одной клаузе ставим ребра (полный подграф — треугольник для трёхлитеральной клаузе). Это гарантирует, что независимое множество может выбрать максимум одну вершину из каждой клаузе.
- Для любых двух вершин, соответствующих литералам $x$ и $\neg x$ (противоположные литералы одного и того же переменного) из разных клауз, добавляем между ними ребро. Это не даёт выбрать в независимом множестве одновременно противоречивые литералы.
- Параметр $k$ берём равным числу клауз $m$.
Корректность:
- Если $\varphi$ выполнима, то есть присвоение переменным, делающее каждую клаузу истинной. Для каждой клаузи выбираем один истинный литерал; соответствующие вершины по построению не соединены ребром: внутри клаузи мы взяли только одну вершину (ребра внутри клаузи предотвращают выбор двух), а между клаузами нет рёбер между выбранными вершинами, потому что выбранные литералы не являются противоположностями (противоречивые литералы не могут быть одновременно истинны). Значит существует независимое множество размера $m$.
- Обратно, если в $G$ есть независимое множество размера $m$, то в каждой клаузе оно должно содержать ровно одну вершину (иначе максимум из одной из клауз). Эти выбранные вершины соответствуют литералам, не являющимся противоположностями (иначе между ними было бы ребро). Присвоив соответствующим литералам значение «истина» (и остальным — произвольно), получаем модель формулы, то есть $\varphi$ выполнима.
Полиномиальность: граф строится за время полиномиальное по размеру формулы, число вершин и рёбер полиномиально ограничено ($O(m)$ вершин и $O(m^2)$ рёбер в худшем случае).
Вывод: поскольку $3$-SAT сводится полиномиально к решению INDEPENDENT SET, последняя задача NP-трудна; она также принадлежит NP (сертификат — множество вершин размер $k$, проверка независимости и размера — полиномиальна). Значит задача NP-полна. Аналогично можно редуцировать из INDEPENDENT SET в другие оптимизационные задачи, чтобы показать их NP-трудность.
Замечания:
- Для любой новой оптимизационной задачи сначала формализуйте решение-версию; именно её обычно доказывают NP-полной.
- Можно использовать разные исходные NP-полные задачи (3-SAT, CLIQUE, VERTEX-COVER, INDEPENDENT-SET и т.д.), выбирая ту, чей стиль конструкции проще для вашей задачи.