NP-полнота и проблема P=NP

Среди задач NP есть «самые трудные» — NP-полные. Если решить хоть одну из них быстро, рухнут все: это и есть суть вопроса P=NP на миллион долларов.

NP-полная задача — задача из NP, к которой полиномиально сводится любая другая задача из NP. Это «самые трудные» представители класса.

Что значит «самая трудная»

Вспомним сводимость из прошлого раздела, но теперь с полиномиальными редукциями. Задача B называется NP-трудной, если любая задача NP сводится к B за полином. Если вдобавок B сама лежит в NP, она NP-полна. Красота в следствии: если найти полиномиальный алгоритм хотя бы для одной NP-полной задачи, то через редукции все задачи NP станут полиномиальными, и P = NP. И наоборот: если хоть одна NP-полная задача доказанно требует экспоненты — P ≠ NP. NP-полные задачи — «ключ» ко всему классу.

Теорема Кука-Левина и зоопарк задач

В 1971 году Кук (и независимо Левин) доказали, что SAT NP-полна — первая такая задача. Дальше пошла цепная реакция: сводя SAT к новым задачам, доказали NP-полноту тысяч задач. Знаменитый список:

Все они эквивалентны по трудности: реши одну за полином — решишь все.

Сведение как доказательство NP-трудности

Покажем механику: сведём 3-раскраску к SAT (идея кодирования). Для каждой вершины — переменные «вершина имеет цвет c», добавляем условия «ровно один цвет» и «соседи разного цвета». Проиллюстрируем кодирование ограничений в булевы переменные.

# кодируем 3-раскраску графа в булевы переменные для SAT
# переменная x[(v,c)] = вершина v окрашена в цвет c (c in 0,1,2)
edges = [("A","B"), ("B","C"), ("A","C")]   # треугольник
vertices = ["A", "B", "C"]
colors = [0, 1, 2]

clauses = []
# 1) каждая вершина имеет хотя бы один цвет
for v in vertices:
    clauses.append([f"x_{v}_{c}" for c in colors])
# 2) соседи не одного цвета: not(x_u_c and x_v_c)
for (u, v) in edges:
    for c in colors:
        clauses.append([f"NOT x_{u}_{c}", f"NOT x_{v}_{c}"])

print("переменных:", len(vertices) * len(colors))
print("клауз (ограничений):", len(clauses))
print("пример клаузы (вершина A имеет цвет):", clauses[0])
print("пример клаузы (ребро A-B, цвет 0):", clauses[3])

Вывод:

переменных: 9
клауз (ограничений): 12
пример клаузы (вершина A имеет цвет): ['x_A_0', 'x_A_1', 'x_A_2']
пример клаузы (ребро A-B, цвет 0): ['NOT x_A_0', 'NOT x_B_0']

Задача раскраски превратилась в SAT-формулу за полином. Решив SAT, мы решили бы раскраску — это и есть редукция, доказывающая NP-трудность.

Проблема P=NP на миллион долларов

Вопрос P =? NP — главная открытая проблема информатики и одна из семи «задач тысячелетия» с премией в миллион долларов. Если P = NP, то для всех NP-задач (взлом шифров, оптимизация, доказательство теорем) есть быстрые алгоритмы — это перевернуло бы мир (и сломало бы криптографию). Большинство учёных верит, что P ≠ NP (проверить решение всё же легче, чем найти), но доказательства нет уже более 50 лет. Связь с олимпиадами: когда на контесте задача оказывается NP-полной, грамотный участник не ищет полиномиальное решение (его, вероятно, нет), а применяет переборы с отсечениями, эвристики, динамику по подмножествам, приближённые алгоритмы. Распознать NP-полноту — ценный навык.

Как работает под капотом

Почему NP-полные задачи так связаны? Теорема Кука-Левина показывает, что работа любой недетерминированной полиномиальной машины кодируется булевой формулой (SAT). Значит, SAT «содержит» все NP-задачи. А раз SAT сводится к раскраске, рюкзаку и прочим, то и они универсальны. Это удивительное единство: тысячи внешне разных задач — на самом деле одна задача в разных костюмах. На практике это спасает: для NP-полных задач написаны мощные общие SAT-решатели, и реальную задачу часто проще свести к SAT, чем изобретать свой алгоритм.

Частые ошибки

«NP-полная = нерешаемая». Нет, решаемая (перебором), просто, вероятно, не за полином. И на практике многие экземпляры решаются эвристиками быстро.

Путать NP-трудную и NP-полную. NP-полная = NP-трудная И лежит в NP. Бывают NP-трудные задачи вне NP (даже неразрешимые).

Искать полиномиальный алгоритм для NP-полной задачи на контесте. Если задача NP-полна, ищите перебор/эвристику — полиномиального решения, скорее всего, не существует.

Итог

• NP-полная задача — из NP, к которой полиномиально сводится любая задача NP; «самые трудные» в NP.
• SAT первой доказана NP-полной (Кук-Левин); через редукции NP-полны раскраска, клика, коммивояжёр, рюкзак и тысячи других.
• Решить одну NP-полную за полином ⇒ P = NP; это открытая проблема тысячелетия (миллион долларов).
• На олимпиадах распознавание NP-полноты подсказывает переходить к перебору, эвристикам и приближениям.