Определение NP‑полноты:
- Язык (задача) $L$ называется NP‑полным, если
1. $L\in \mathrm{NP}$ (решение проверяется детерминированно за полином),
2. для любой задачи $A\in \mathrm{NP}$ существует полиномиальная сводимость (полиномиально вычислимая функция) $f$ такая, что для любого входа $x$ $$x\in A⟺f(x)\in L.$$ Это называется полиномиальной много‑в‑одном сводимостью (many‑one). (Cook–Levin: SAT — с.н.с. NP.)
Пример сводимости SAT → Задача рюкзака (через Subset‑Sum):
- Схема (классическая идея): сначала привести SAT к 3‑SAT. Пусть дано 3‑SAT с переменными $x_1,\dots ,x_n$ и дизъюнктами (клауза) $C_1,\dots ,C_m$.
- Построим экземпляр SUBSET‑SUM (подмножество сумм), затем заметим, что SUBSET‑SUM сводится к 0–1 knapsack тривиально.
Построение (эсквиз):
1. Выбираем основание $B>m$ (например $B=m+1$), чтобы при сложении цифр не было переносов.
2. Числа будут иметь $n+m$ «цифр»: первые $n$ цифр соответствуют выбору значения для каждой переменной, последние $m$ — выполнению клауз.
3. Для каждой переменной $x_i$ создаём два числа $a_{i,T}$ и $a_{i,F}$. В $i$-й (переменной) позиции обе эти числа имеют цифру $1$ (это обеспечивает выбор ровно одного значения для каждой переменной), а в позициях клауз у числа стоит $1$ там, где соответствующая литерала (например $x_i$ или $\neg x_i$) входит в клаузу.
4. Для каждой клаузулы добавляем вспомогательные «заполняющие» числа, чтобы можно было довести суммарную цифру в каждой клаузовой позиции до заданного целевого значения (обычно «1») ровно тогда, когда выбран хотя бы один истинный литерал в этой клаузе.
5. Целевое число $T$ задаём так, чтобы первые $n$ цифр = $1$ (обеспечить ровно один выбор значения на переменную), последние $m$ цифр = требуемые значения для клауз (например $1$).
- Правильность: существует подмножество чисел, сумма которого равна $T$ тогда и только тогда, когда в 3‑SAT есть удовлетворящее присваивание (выбор одного из $a_{i,T},a_{i,F}$ для каждой переменной и подбор заполняющих чисел обеспечивает каждую клаузу).
- Затем SUBSET‑SUM сводится к 0–1 KNAPSACK: взять веса = эти числа, вместимость = $T$, доходы равны весам и требовать достижение ровно вместимости (или задать доход‑порог). Таким образом получаем сводимость SAT ≤p KNAPSACK.
Эвристики и приближённые алгоритмы на практике (коротко и по назначению):
- Жадные алгоритмы (greedy): просты и быстры; часто дают хорошее начальное решение (например жадный по плотности $value/weight$ для рюкзака).
- Локальный поиск: hill‑climbing, simulated annealing, tabu search — быстро улучшают решение на больших экземплярах.
- Популяционные/эволюционные алгоритмы и метаэвристики: genetic algorithms, GRASP — применимы, когда пространство решений сложно.
- Линейное программирование и округление: решаем LP‑релаксацию, затем округляем; даёт гарантии через интегральный разрыв.
- Прямые алгоритмы с ветвлением и отсечением (branch‑and‑bound / branch‑and‑cut): точные методы с сильными эвристиками и оценками (используются в солверах).
- Специальные аппроксимации и схемы: для KNAPSACK есть FPTAS — для любого $\epsilon >0$ можно получить решение с ценностью не менее $(1-\epsilon )\mathrm{OPT}$ за время полиномиальное в $n$ и $1/\epsilon$ (т.е. $\mathrm{poly}(n,1/\epsilon )$).
- Для других задач: PTAS, константные аппроксимации (например $0.878\dots$ для Max‑Cut по Goemans–Williamson с SDP), приближения через специализированные эвристики.
Как оценивать качество эвристики/приближения:
- Аппроксимационное отношение (approximation ratio). Для задачи максимизации определить
$$\rho =\frac{\mathrm{ALG}}{\mathrm{OPT}},$$ где $\mathrm{ALG}$ — значение алгоритма, $\mathrm{OPT}$ — оптимум. Алгоритм считается $\alpha$-аппроксимационным, если для всех входов $\mathrm{ALG}\ge \alpha \cdot \mathrm{OPT}$.
Для минимизации обычно берут $\rho =\frac{\mathrm{OPT}}{\mathrm{ALG}}$.
- Относительная погрешность (relative gap): $(\mathrm{OPT}-\mathrm{ALG})/\mathrm{OPT}$.
- Гарантии на время: полиномиальность, зависимость от $1/\epsilon$ (для FPTAS).
- Интегральный разрыв LP: насколько хороша LP‑релаксация — даёт теоретическую оценку округления.
- Эмпирическая оценка: бенчмарки, сравнение с оптимумом на малых экземплярах (или с лучшими известными решениями), статистика по набору инстансов (средняя/худшая/медианная разница), стабильность и время.
- Вероятностные гарантии: для рандомизированных алгоритмов смотреть вероятность достижения требуемого соотношения/предела.
Краткое резюме:
- NP‑полнота = принадлежность NP + полиномиальная сводимость из любой задачи NP.
- Практически для SAT→Knapsack используют серию сводимостей (SAT→3‑SAT→SUBSET‑SUM→KNAPSACK) через кодирование присваиваний в числа; Subset‑Sum легко превращается в knapsack.
- На практике применяют комбинацию жадных эвристик, локального поиска, LP‑релаксаций, метаэвристик и точных методов с отсечением; качество оценивают теоретическими гарантиями (аппрокс‑коэффициент, FPTAS/PTAS) и эмпирическими метриками (относительная ошибка, бенчмарки, время).