NP-полнота

Цели урока

• Понимать утверждение теоремы Кука-Левина и идею доказательства
• Читать и составлять формулы в CNF, решать SAT вручную на малых примерах
• Строить полиномиальные редукции и доказывать их корректность
• Применять рецепт доказательства NP-полноты к новым задачам

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

• Классы P и NP

P vs NP - единственный открытый вопрос информатики с призом 1 000 000 долларов (Clay Mathematics Institute). Сатоши Накамото построил Bitcoin на предположении что P!=NP. Если кто-то докажет P=NP - криптография сломана, Bitcoin умер. В 1971 году Стивен Кук нашёл задачу в центре этой загадки.

• **Верификация чипов (Intel, Cadence)** - SAT solvers проверяют корректность процессоров с миллиардами транзисторов; без NP-теории инструмент не существовал бы
• **Криптография** - RSA и ECC основаны на NP-hard задачах (факторизация, дискретный логарифм); P=NP сломает всю криптографию
• **Планирование и логистика** - vehicle routing, job scheduling - NP-полные задачи; Amazon и UPS решают их приближённо с миллиарддолларовой экономией
• **SAT в ML** - верификация нейронных сетей (Reluplex, Marabou) сводит свойства сети к SAT/SMT; NP-полнота здесь прямое препятствие
• **Биоинформатика** - сборка генома, protein folding - NP-hard задачи, решаемые эвристиками и специализированными приближениями

Кук 1971 - открытие чёрной дыры в центре сложности

Стивен Кук был аспирантом, когда доказал NP-полноту SAT в 1971 году. Его статья 'The Complexity of Theorem-Proving Procedures' задала направление всей теории сложности. Параллельно в СССР Леонид Левин независимо получил тот же результат - он сформулировал понятие 'универсальная переборная задача', предвосхитив концепцию NP-полноты. Ричард Карп в 1972 году расширил список до 21 задачи, показав что NP-полнота не экзотика - она повсюду. Кук получил премию Тьюринга в 1982 году.

Теорема Кука-Левина

**1971. Стивен Кук задаёт вопрос: есть ли в NP самая трудная задача - такая, что решив её за полином, решишь всё NP?** Ответ - да. Эта задача называется SAT. Не потому что Boolean satisfiability особенная. Потому что любую NP-задачу можно закодировать как SAT. Один SAT solver - и весь класс NP под рукой.

Теорема Кука-Левина (1971): задача **SAT** (Boolean Satisfiability) является **NP-полной**. Это означает: (1) SAT в NP, (2) любая задача из NP сводится к SAT за полиномиальное время. Если SAT в P, то P = NP.

Значение теоремы выходит за пределы теории. SAT solver может решить любую NP-задачу через кодирование. Поэтому промышленные SAT solvers - MiniSat, CaDiCaL, Kissat - применяются для верификации чипов Intel, планирования спутников NASA, криптоанализа. Теорема Кука превратила SAT в ассемблерный язык NP.

Задача SAT

**SAT (Boolean Satisfiability)**: дана булева формула в CNF. Существует ли набор значений переменных, при котором она истинна? Brute force: 2^n вариантов для n переменных. Для n = 100 это 10^30. Нереально. Но современные SAT solvers решают формулы с миллионами переменных - и именно на этом стоит вся промышленная верификация.

Формула в **CNF** (конъюнктивная нормальная форма): phi = C1 AND C2 AND ... AND Cm, где каждая клауза Ci = (l1 OR l2 OR ...) - дизъюнкция литералов. Литерал - переменная xj или её отрицание NOT xj. SAT принимает формулу в CNF и отвечает: выполнима или нет.

Промышленные SAT solvers (MiniSat, CaDiCaL) используют DPLL/CDCL: unit propagation, clause learning, non-chronological backtracking. Worst case остаётся экспоненциальным, но на формулах из реальных задач они отрабатывают за секунды на миллионах переменных. Именно поэтому Cadence и Intel верифицируют чипы с миллиардами транзисторов через SAT.

Полиномиальные редукции

**Как доказать, что задача B не легче A?** Через редукцию: полиномиальное преобразование любого экземпляра A в экземпляр B. Если B решается за полином - A тоже. Контрапозитив: если A трудна, то и B трудна. Это инструмент переноса сложности без нового доказательства с нуля.

Полиномиальная редукция (Karp reduction): A <=_p B, если существует полиномиально вычислимая функция f такая, что x в A тогда и только тогда когда f(x) в B. Интуиция: 'задача A не труднее задачи B' - решатель B может решить и A.

NP-полнота

**Задача L NP-полна** - это означает два условия одновременно: L в NP (решение проверяется за полином) и для каждой задачи A в NP выполняется A <=_p L. NP-полные задачи - самые трудные в NP. Если одна из них попадёт в P - весь класс NP коллапсирует в P.

NP-complete = NP INTERSECT NP-hard. **NP-hard** - задачи, к которым сводится всё NP (не обязательно сами в NP). **NP-complete** - NP-hard задачи, которые ещё и в NP. Если хотя бы одна NP-полная задача в P - значит P = NP.

Рецепт доказательства NP-полноты новой задачи L: 1. показать L в NP - построить полиномиальный верификатор 2. взять уже известную NP-полную задачу Q и показать Q <=_p L. Благодаря транзитивности редукций: если Q NP-полна и Q <=_p L, то все NP <=_p L.

После Кука (1971) Ричард Карп в 1972 году показал NP-полноту 21 задачи - Clique, Vertex Cover, Hamiltonian Cycle, 3-SAT, Partition. Сегодня известны тысячи NP-полных задач из комбинаторики, теории графов, биоинформатики, криптографии. Каждый новый домен приносит новые NP-полные задачи.

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

• **Теорема Кука-Левина (1971)**: SAT - первая NP-полная задача; любая NP-задача полиномиально сводится к SAT
• **SAT**: дана булева формула в CNF, существует ли выполняющий набор? Brute force O(2^n), практика - CDCL solvers
• **Редукция A <=_p B**: полиномиальное преобразование входов, x в A тогда и только тогда когда f(x) в B
• **NP-complete = NP INTERSECT NP-hard**: если одна NP-полная задача в P, то P = NP
• Карп 1972: 21 NP-полная задача. Сегодня - тысячи, включая TSP, Knapsack, Graph Coloring
• NP-полнота - результат о worst case, не невозможности: эвристики, приближения, SAT solvers работают на практике

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

NP-полнота - центральное понятие теории сложности:

• Классы P и NP — Фундамент - определения P, NP, верификации
• Классические NP-полные задачи — Конкретные примеры: 3-SAT, Clique, Hamiltonian, Subset Sum
• Машина Тьюринга — NTM из доказательства Кука-Левина - формальная основа

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

• Если завтра докажут P = NP, какие области пострадают первыми? Какие выиграют?
• Почему редукция должна быть полиномиальной? Что произойдёт, если допустить экспоненциальные редукции?
• SAT solvers решают практические задачи с миллионами переменных. Как это сочетается с NP-полнотой? (Подсказка: worst case vs average case)

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

• cplx-01 — Определения P, NP и верификации заданы в предыдущем уроке
• cplx-03 — Классические NP-полные задачи: 3-SAT, Clique, Hamiltonian
• comp-02 — TM-модель лежит в основе доказательства Кука-Левина
• alg-34-approximation — Приближённые алгоритмы нужны именно для NP-полных задач
• ml-09-gradient-descent — Gradient descent обходит NP-hard оптимизацию в ML практически
• isd-08-database-selection
• alg-01-big-o