NP-повнота: як SAT, 3-COLOR і TSP таємно є однією і тією ж задачею
Немає відомого ефективного алгоритму для задачі комівояжера, розфарбування графа чи булевої задачі виконуваності — і це не через брак спроб. Редукції — це техніка доведення, яка показує, що всі ці задачі, у точному сенсі, є однією й тією ж задачею в різних маскуваннях.
P, NP та NP-важкі задачі
P — клас задач розпізнавання, розв'язних за поліноміальний час. NP — клас задач розпізнавання, чиї розв'язки можна перевірити за поліноміальний час — навіть якщо знаходження такого розв'язку може зайняти експоненційно багато часу. Кожна задача з P тривіально належить NP (якщо можна швидко розв'язати — можна й швидко перевірити розв'язок), але чи P = NP — найвідоміша відкрита проблема інформатики.
Задача є NP-важкою, якщо будь-яку задачу з NP можна звести до неї за поліноміальний час — неформально, вона «принаймні настільки ж складна, як усе в NP». Задача, яка одночасно NP-важка і сама належить NP, називається NP-повною.
P = NP ? відкрито — проблема тисячоліття вартістю $1,000,000
NP-повна = NP ∩ NP-важка
Поліноміальні редукції
Поліноміальна редукція задачі A до задачі B (позначається A ≤ₚ B) — це поліноміальний алгоритм, який перетворює будь-який екземпляр A на екземпляр B так, що відповідь на екземпляр B дає відповідь на екземпляр A. Ключовий логічний наслідок:
Контрапозиція: якщо A NP-важка і A ≤ₚ B, то B теж NP-важка
Редукції передають складність «вперед» — саме так будується вся мережа NP-повних задач з однієї початкової задачі
Саме ця стратегія використовується для доведення NP-повноти нових задач: замість розробки алгоритму з нуля показують, що відома NP-повна задача зводиться до неї.
Кук-Левін: SAT є NP-повною
Теорема Кука-Левіна (1971) — насіння всього дерева редукцій: вона доводить, що булева виконуваність (SAT) є NP-повною напряму, симулюючи історію обчислення довільної поліноміальної недетермінованої машини Тюрінга у вигляді гігантської булевої формули. Будь-яке приймаюче обчислення машини відповідає виконуваному присвоєнню, і навпаки.
3-SAT — де кожен диз'юнкт містить рівно 3 літерали — теж NP-повна (SAT зводиться до 3-SAT розбиттям довгих диз'юнктів допоміжними змінними), і є найпоширенішою відправною точкою для редукцій, оскільки її однорідну структуру легко закодувати в інші комбінаторні задачі.
(x₁ ∨ x̄₂ ∨ x₃) ∧ (x̄₁ ∨ x₂ ∨ x̄₃) ∧ (x₂ ∨ x₃ ∨ x̄₁)
Питання: чи існує присвоєння x₁,x₂,x₃ ∈ {так,ні}, що робить кожен диз'юнкт істинним?
Редукція 3-SAT до 3-COLOR
3-розфарбування графа запитує: чи можна розфарбувати вершини графа трьома кольорами так, щоб жодне ребро не з'єднувало дві вершини одного кольору? Класична редукція з 3-SAT будує три гаджети:
- Базовий трикутник: три спеціальні вершини T (Так), F (Ні), B (База), взаємно з'єднані, фіксуючи три різні «еталонні кольори».
- Гаджет змінної: для кожної змінної xᵢ трикутник {xᵢ, x̄ᵢ, B} змушує xᵢ та x̄ᵢ приймати колір T або F — але ніколи однаковий, точно кодуючи «xᵢ істинна XOR xᵢ хибна».
- Гаджет диз'юнкту (OR-гаджет): для кожного диз'юнкту (a ∨ b ∨ c) невеликий гаджет із 6 вершин, з'єднаний з літералами a, b, c та з вершинами T/F, побудований так, що він 3-розфарбовуваний тоді й лише тоді, коли принаймні один з a, b, c пофарбований у T.
Формула 3-SAT виконувана ⟺ побудований граф 3-розфарбовуваний
Редукція 3-SAT до TSP (через гамільтонів цикл)
Задача комівояжера (версія розпізнавання: «чи існує маршрут довжиною ≤ k?») зазвичай доводиться NP-важкою у два кроки: 3-SAT зводиться до гамільтонового циклу (чи існує цикл, що відвідує кожну вершину рівно один раз?), а гамільтонів цикл тривіально зводиться до TSP.
Крок 1 — Гамільтонів цикл зводиться до TSP
Маючи граф G, побудуємо повний зважений граф G' на тих самих вершинах: ребра, присутні в G, отримують вагу 1, усі інші ребра — вагу 2. G має гамільтонів цикл тоді й лише тоді, коли G' має маршрут із загальною вагою рівно n (використовуючи лише ребра вагою 1):
Маршрут TSP вагою n існує в G' ⟺ гамільтонів цикл існує в G
Крок 2 — 3-SAT зводиться до гамільтонового циклу
Ця редукція (авторства Карпа, 1972) складна: кожна змінна xᵢ представлена гаджетом «скрученої драбини» з двома можливими напрямками проходу (що відповідають xᵢ = істина або хибність), а кожен диз'юнкт представлений вершиною-з'єднувачем, яку можна відвідати лише «позичивши» прохід в одного з трьох гаджетів своїх літералів — змушуючи принаймні один літерал у кожному диз'юнкті пройти у «виконуваному» напрямку.
| Ланцюг редукцій | Що встановлюється |
|---|---|
| 3-SAT ≤ₚ Гамільтонів цикл | Гам. цикл NP-важкий |
| Гамільтонів цикл ≤ₚ TSP | TSP (розпізнавання) NP-важка |
| TSP ∈ NP | кандидатський маршрут перевіряється за O(n) |
| ⟹ TSP є NP-повною |
Що NP-повнота означає на практиці
Доведення NP-повноти задачі — не глухий кут, а корисна інформація. Вона говорить вам:
- Не витрачайте час на пошук точного поліноміального алгоритму — тисячі дослідників безуспішно намагалися це зробити для споріднених задач з 1970-х років.
- Експоненційний точний алгоритм найгіршого випадку (branch-and-bound, DPLL для SAT) все ще може бути прийнятним для розмірів екземплярів, з якими ви реально працюєте.
- Для багатьох NP-важких задач оптимізації існують апроксимаційні алгоритми з доведеними гарантіями (наприклад, 1.5-апроксимація Крістофідеса для метричного TSP).
- Спеціальна структура (планарні графи, обмежена деревна ширина, низька щільність диз'юнктів) може зробити інакше складні екземпляри розв'язними.
Життя з NP-складністю: евристики
Для екземплярів, надто великих для точних методів, практики звертаються до евристик, що обмінюють гарантії оптимальності на швидкість:
| Задача | Поширена евристика | Типова якість |
|---|---|---|
| TSP | Найближчий сусід + 2-opt | ~5% над оптимумом |
| TSP | Генетичний / Лін-Кернігана | <1% над оптимумом |
| 3-SAT | WalkSAT (локальний пошук) | Розв'язує більшість практичних екземплярів |
| Розфарбування графа | Жадібний + порядок DSATUR | Зазвичай у межах кількох кольорів від оптимуму |
🤝 Подивитись, як евристики борються з NP-складністю
Порівняйте жадібний, 2-opt та генетичний алгоритми розв'язання задачі комівояжера