Формальные языки
NP-полнота: доказательства сведений
1972 год. Ричард Карп публикует список из 21 задачи - все NP-complete через цепочки сведений. За год до этого Стивен Кук доказал NP-полноту SAT. Карп показал: тысячи задач, над которыми работали математики и инженеры, все связаны - решить одну значит решить все. Это самое важное открытие в теории алгоритмов.
- **Intel формальная верификация:** SAT-солверы (CaDiCaL, Kissat) используются для верификации процессорных чипов. Каждое новое поколение Intel Core проверяется на соответствие спецификации через тысячи SAT-запросов. NP-complete задача решается в производстве
- **Google OR-Tools:** библиотека для решения NP-hard задач оптимизации (vehicle routing, job scheduling, bin packing). Используется в Google Maps маршрутизации, Waymo планировании, производственном расписании
- **Биоинформатика (protein-protein interaction):** нахождение максимальной клики в графе взаимодействий белков. Клика - NP-complete. На практике: специальные алгоритмы для биологических графов (обычно разреженные) + FPT-алгоритмы
- **Compiler register allocation:** раскраска графа вмешательств (interference graph) - 3-Coloring NP-complete. LLVM использует Chaitin algorithm (жадная эвристика) + spilling. Практически работает для реальных программ несмотря на NP-полноту
SAT и теорема Кука-Левина
**SAT** (satisfiability): дана булева формула φ(x₁, ..., xₙ), существует ли присваивание переменным, делающее φ истинной? 1971 год: Стивен Кук доказывает, что SAT NP-полна - любая задача из NP polynomial-time сводится к SAT. Это означает: SAT - самая трудная задача в NP.
**NP-полнота:** задача X является NP-полной если (1) X ∈ NP и (2) для любой Y ∈ NP: Y ≤pₘ X (все NP-задачи сводятся к X). Задача X является NP-hard если выполняется (2) без ограничения (1). NP-hard может быть вне NP.
SAT NP-полна означает что...
3-SAT и редукции
**3-SAT** - SAT где каждый клоз содержит ровно 3 литерала. SAT ≤pₘ 3-SAT (сведение за poly). 3-SAT проще для сведений к другим задачам - стандартный промежуточный шаг в цепочках. Кстати, 2-SAT ∈ P (решается за O(n+m) через SCC в графе импликаций)!
Граница между 2-SAT (P) и 3-SAT (NP-complete) - один из самых чётких примеров того, как маленькое изменение в задаче переводит её из P в NP. Аналогично: поиск пути в графе (P) vs Hamiltonian path (NP-complete). Клика размера 2 (ребро, P) vs клика размера k (NP-complete при k часть входа).
2-SAT решается за O(n+m), 3-SAT NP-complete. Что меняется при увеличении клоза с 2 до 3?
Классические NP-полные задачи
Список Карпа (1972): 21 NP-полная задача, включая Vertex Cover, Clique, Independent Set, TSP, Hamiltonian Path, Set Cover, Graph Coloring. Все связаны цепочками poly-time сведений. Сегодня базы данных содержат тысячи NP-полных задач из комбинаторики, биологии, физики, логики.
| Задача | Вопрос | Практическое применение |
|---|---|---|
| 3-SAT | Выполнима ли 3-КНФ формула? | SAT-солверы, верификация схем |
| Vertex Cover | Есть ли покрытие вершинами размера k? | Сетевой мониторинг, дизайн сетей |
| Clique | Есть ли клика размера k? | Обнаружение сообществ, биоинформатика |
| TSP (decision) | Есть ли тур длины <= L? | Логистика, маршрутизация |
| 3-Coloring | Можно ли раскрасить граф 3 цветами? | Составление расписаний, register allocation |
| Knapsack | Можно ли набрать ценность >= V при весе <= W? | Планирование ресурсов, финансы |
| Set Cover | Можно ли покрыть U множествами числом <= k? | Покрытие сетей, реклама |
**Independent Set ≡ Vertex Cover ≡ Clique** по дополнению: S - independent set в G тогда и только тогда, когда S - clique в дополнении G. Vertex Cover + Independent Set = V (дополнение одного - другое). Это объясняет почему все три задачи NP-complete: одна и та же трудность в разных обличиях.
Vertex Cover и Independent Set NP-complete в общем графе. Что если граф - дерево?
Как доказывать NP-полноту
Стандартный рецепт доказательства NP-полноты задачи X: (1) Показать X ∈ NP (верификатор за poly). (2) Выбрать известную NP-complete задачу Y. (3) Построить poly-time reduction Y ≤pₘ X. (4) Доказать корректность: y ∈ Y ⟺ f(y) ∈ X.
**Parameterized complexity** - современное уточнение: задача X **FPT** (fixed-parameter tractable) если существует алгоритм O(f(k) · poly(n)) для параметра k. Vertex Cover FPT по k (алгоритм O(2^k · n)). Это важно для реальных задач: если k мало (небольшое vertex cover), задача решается быстро.
NP-полные задачи всегда требуют экспоненциального времени - их нельзя решать быстро
NP-полные задачи часто решаются эффективно на практике через SAT-солверы (CDCL), аппроксимации, parameterized algorithms или специальные структуры входных данных
SAT-солверы (Z3, MiniSAT, CaDiCaL) решают промышленные SAT-задачи с миллионами переменных за секунды. Это не противоречие: NP-completeness - о наихудшем случае. Практические задачи часто имеют структуру, которую CDCL эксплуатирует. TSP решается точно для тысяч городов через branch-and-bound.
Нужно доказать NP-полноту новой задачи X. Первый шаг - показать X ∈ NP. Зачем?
Итоги
- **NP-полнота:** X ∈ NP + X NP-hard (все NP задачи poly-сводятся к X). SAT - первая NP-полная задача (Кук, 1971)
- **Рецепт доказательства:** (1) X ∈ NP (poly верификатор), (2) Y ≤pₘ X для известной NP-complete Y, (3) доказать корректность редукции
- **2-SAT vs 3-SAT:** граница P/NP по количеству литералов в клозе. 2-SAT ∈ P через SCC, 3-SAT NP-complete
- **Практика:** NP-complete не значит 'всегда медленно'. SAT-солверы, FPT-алгоритмы, специальные структуры позволяют решать NP-задачи в реальности
Связанные темы
NP-полнота - центральная концепция теории сложности:
- P vs NP — NP-полные задачи - самые трудные в NP. Poly для любой из них = P = NP
- Сведения — Poly-time mapping reductions - инструмент доказательства NP-полноты
- Приближённые алгоритмы — Если задача NP-complete, аппроксимация - практическая альтернатива
Вопросы для размышления
- Vertex Cover на деревьях решается за O(n) DP, но NP-complete на общих графах. Что именно в структуре дерева делает задачу лёгкой?
- SAT-солверы решают промышленные SAT-задачи с миллионами переменных. Означает ли это, что SAT фактически в P для практических задач?
- Если бы P = NP был доказан с алгоритмом O(n^10^100), что изменилось бы в криптографии? В формальной верификации?