Классические NP-полные задачи

Цели урока

• Понимать 3-SAT и её роль как «компилятора» редукций
• Читать редукцию 3-SAT <=_p CLIQUE через граф литералов
• Различать гамильтонов и эйлеров цикл - и почему один в P, другой NP-полный
• Объяснять псевдо-полиномиальность DP для Subset Sum

Предварительные знания

• NP-Completeness

Amazon, 2005. Команда маршрутизации доставки: 1000 водителей, 50 000 адресов ежедневно. Каждый водитель объезжает свой список - это Hamilton Path. Оптимальное решение - NP-hard. Amazon использует Lin-Kernighan heuristic и сокращает пробег на 15%, экономя десятки миллионов литров топлива в год. NP-полнота не остановила бизнес - она определила, какой алгоритм использовать.

• **Логистика и маршрутизация** - TSP и Vehicle Routing используются Amazon, UPS, FedEx ежедневно
• **Компиляторы** - Register Allocation = Graph Coloring (NP-полная), решается эвристиками Chaitin
• **Криптография** - Subset Sum лежит в основе некоторых схем шифрования (Merkle-Hellman knapsack)

Кук, Левин и рождение NP-полноты

В 1971 году Стивен Кук из Университета Торонто опубликовал статью «The complexity of theorem-proving procedures», где доказал NP-полноту SAT и ввёл само понятие NP-полноты. Независимо в СССР Леонид Левин пришёл к тем же выводам в 1973 году - задача теперь называется теоремой Кука-Левина. Кук получил премию Тьюринга в 1982 году. Ричард Карп в 1972 году показал NP-полноту 21 конкретной задачи - включая CLIQUE, Hamilton Cycle и Subset Sum - заложив основу всего, что изучается в этом уроке.

3-SAT

**3-SAT** - ограниченная версия SAT, где каждая клауза содержит **ровно 3 литерала**. Ограничение должно было упростить задачу. Не упростило - 3-SAT остаётся NP-полной. При этом **2-SAT** (клаузы по 2 литерала) - в P! Граница сложности проходит именно между 2 и 3.

3-SAT: формула phi = C1 AND C2 AND ... AND Cm, где каждая Ci = (l1 OR l2 OR l3). NP-полнота доказывается редукцией SAT <=_p 3-SAT: любую клаузу с k > 3 литералами можно разбить на клаузы по 3 с помощью вспомогательных переменных.

3-SAT - «рабочая лошадка» редукций. Большинство NP-полных задач доказываются через редукцию из 3-SAT, потому что три литерала на клаузу - удобная структура для кодирования ограничений. 3-SAT - это «компилятор» из логики в комбинаторику.

Задача о клике (CLIQUE)

**CLIQUE**: дан граф G и число k. Существует ли в G **полный подграф** (клика) из k вершин - то есть k вершин, каждая пара которых соединена ребром? Для социальной сети: есть ли группа из k людей, где все друг друга знают?

CLIQUE NP-полна. Доказательство через 3-SAT <=_p CLIQUE: для формулы с m клаузами строим граф, где вершины - литералы в клаузах, рёбра - между совместимыми литералами из разных клауз. Клика размера m соответствует выполняющему набору.

Связанные задачи: **Independent Set** (максимальное множество без рёбер) - дополнение клики. **Vertex Cover** (минимальное покрытие рёбер) - дополнение independent set. Все три NP-полны и связаны простыми редукциями через дополнение графа.

Гамильтонов путь

**Hamiltonian Path/Cycle**: существует ли в графе путь (цикл), проходящий через **каждую вершину ровно один раз**? Не путать с эйлеровым путём, который проходит через каждое **ребро** один раз - эйлеров путь находится за O(E), а гамильтонов - NP-полная задача.

Hamiltonian Cycle NP-полна. Проверка (верификация): дана последовательность вершин, проверить что это цикл через все вершины - O(V). Нахождение: brute force - O(V!) перестановок. Важно: Euler Cycle в P (условие: все степени чётные), Hamilton Cycle NP-complete.

Практическое значение: задача коммивояжёра (TSP) - это поиск кратчайшего гамильтонова цикла. TSP - одна из самых изученных NP-полных задач. Для неё существуют приближённые алгоритмы: Christofides (1.5-приближение для метрического TSP), Lin-Kernighan эвристика. На практике решают экземпляры с десятками тысяч городов.

Subset Sum

**Subset Sum**: дано множество чисел S = {s1, ..., sn} и целевая сумма t. Существует ли подмножество S, сумма элементов которого равна t? Кажется простой задачей, но она NP-полна. Интересно, что динамическое программирование даёт **псевдо-полиномиальный** алгоритм.

Subset Sum NP-полна (через редукцию из 3-SAT). Brute force: O(2^n) подмножеств. DP-решение: O(n*t), где t - целевая сумма. Это **псевдо-полиномиальное** время: полиномиально от значения t, но экспоненциально от длины записи t (log t бит).

Псевдо-полиномиальность - тонкий момент. Алгоритм O(n*t) кажется полиномиальным, но размер входа - O(n*log(max_s)), а t может быть экспоненциально большим (t = 2^n). Для задач, где числа «маленькие» (t = poly(n)), DP работает отлично. Для «больших» чисел - задача остаётся трудной.

NP-полные задачи встречаются повсюду - в логистике, scheduling, компиляторах, биоинформатике. Для каждой из них нет быстрого точного алгоритма (при P != NP). Но есть приближённые алгоритмы, эвристики, SAT solvers и параметризованная сложность. NP-полнота - не конец пути, а начало поиска практических решений.

Ключевые идеи

• **3-SAT**: клаузы по 3 литерала - NP-полная, хотя 2-SAT в P (фазовый переход сложности)
• **CLIQUE**: поиск полного подграфа размера k - NP-полна через редукцию из 3-SAT
• **Hamiltonian Cycle**: путь через все вершины - NP-полна; не путать с Euler (P)
• **Subset Sum**: подмножество с заданной суммой - NP-полна, но имеет DP O(n*t)

Связанные темы

Классические NP-полные задачи - мост между теорией и практикой:

• NP-полнота — Определения NP-полноты и редукций - теоретический фундамент
• Классы P и NP — Базовые классы сложности - P, NP, верификация

Вопросы для размышления

• Почему граница сложности проходит именно между 2-SAT и 3-SAT? Что такого добавляет третий литерал?
• Если Subset Sum имеет DP-решение за O(n*t), есть ли аналогичные псевдо-полиномиальные алгоритмы для CLIQUE или Hamilton Cycle?
• SAT solvers решают формулы с миллионами переменных. Означает ли это, что P = NP на практике?

Связанные уроки

• cplx-02 — NP-полнота и редукции - теоретический фундамент этого урока
• cplx-01 — Базовые классы P и NP, верификация за полиномиальное время
• cplx-04 — Приближённые алгоритмы строятся на понимании NP-полных задач
• alg-05 — Динамическое программирование - основа псевдо-полиномиальных решений Subset Sum/Knapsack
• comp-04 — Редукции между языками - общий инструмент как для вычислимости, так и для сложности
• alg-07 — Жадные алгоритмы и эвристики - практический ответ на NP-полноту
• ds-01 — Графовые задачи: многие NP-полные задачи - это задачи на графах
• alg-01-big-o