NP-полнота: 21 задача — одна проблема

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

Сначала надо было условиться, что считать хорошим алгоритмом. В 1965 году это независимо сделали Алан Кобэм и Джек Эдмондс: хороший алгоритм — тот, время работы которого ограничено многочленом от длины входа.

Граница проведена не по эстетическим соображениям. Многочлены замкнуты относительно сложения, умножения и подстановки — значит, класс не зависит от того, на какой машине считать и как кодировать вход. А разрыв между многочленом и экспонентой практически непреодолим: при $n=100$ разница между $n^{3}$ и $2^{n}$ — это разница между секундой и временем, превышающим возраст Вселенной в $10^{12}$ раз.

Класс задач, разрешимых за полиномиальное время, обозначают $\mathrm{P}$.

Класс NP

Теперь возьмём задачи, для которых решение легко проверить, даже если непонятно, как его найти.

• Выполнимость. Дана булева формула. Есть ли набор значений переменных, при котором она истинна? Если кто-то принесёт набор — проверка мгновенна.
• Гамильтонов цикл. Есть ли в графе цикл, проходящий через все вершины по разу? Принесённый маршрут проверяется за минуту. Задача — та самая, которую Гамильтон поставил в 1856 году.
• Раскраска в три цвета. Можно ли покрасить вершины графа в три цвета так, чтобы соседние были разными? Проверить раскраску — пройти по рёбрам. Задача — родственница вопроса Гатри о картах.
• Рюкзак. Есть ли в наборе чисел подмножество с заданной суммой?

Класс таких задач обозначают $\mathrm{NP}$. Буквы означают недетерминированно полиномиальные, а вовсе не «не полиномиальные» — это самая частая ошибка в пересказах. Смысл: решение можно угадать и за полиномиальное время проверить.

Очевидно, что $\mathrm{P}\subseteq\mathrm{NP}$: если умеешь найти, умеешь и проверить. Обратное — открытый вопрос.

Кук, 1971

Стивен Кук в Торонто доказал первую теорему о полноте («The Complexity of Theorem-Proving Procedures», 1971).

Идея такая. Работу недетерминированной машины за $T(n)$ шагов можно нарисовать таблицей: строки — моменты времени, столбцы — клетки ленты. Что стоит в каждой клетке таблицы, определяется тремя клетками предыдущей строки — соседками сверху. Значит, всю таблицу можно описать булевой формулой: переменные — «в клетке $(i,j)$ стоит символ $s$», а условия локальны и потому записываются коротко.

Формула выполнима тогда и только тогда, когда машина принимает вход. Так любая задача из $\mathrm{NP}$ сводится к выполнимости.

Задачу, к которой сводится вся $\mathrm{NP}$, называют NP-полной. Кук предъявил первую.

Карп, 1972

Пока была одна NP-полная задача, это выглядело курьёзом логики. Ричард Карп в Беркли показал, что курьёз — правило.

В статье «Reducibility Among Combinatorial Problems» он взял двадцать одну классическую задачу и построил цепочку сведений от выполнимости к каждой. Среди них: целочисленное программирование, клика, вершинное покрытие, покрытие множествами, гамильтонов цикл (ориентированный и нет), хроматическое число, точное покрытие, дерево Штейнера, трёхмерное сочетание, рюкзак, разбиение, расписание, максимальный разрез.

Это список из совершенно разных областей: логика, теория графов, комбинаторная оптимизация, теория расписаний, целочисленное программирование. И все они оказались одной задачей.

Покажем одно сведение целиком — оно короткое и наглядное.

Из выполнимости в независимое множество. Пусть дана формула из $m$ дизъюнктов по три литерала. Построим граф: для каждого дизъюнкта — треугольник из трёх вершин, помеченных его литералами; кроме того, соединим ребром любые две вершины из разных треугольников, помеченные противоположными литералами ($x$ и $\lnot x$).

Утверждение. Формула выполнима тогда и только тогда, когда в графе есть независимое множество размера $m$.

Пусть формула выполнима. В каждом дизъюнкте выберем один истинный литерал и возьмём соответствующую вершину. Взято по одной из каждого треугольника — значит, рёбер треугольников между ними нет; противоположных литералов среди истинных быть не может — значит, нет и рёбер противоречия. Множество независимо, размер $m$.

Обратно: независимое множество размера $m$ содержит не более одной вершины из каждого треугольника, а треугольников ровно $m$ — значит, ровно по одной. Объявим выбранные литералы истинными; это непротиворечиво, потому что противоположные литералы соединены ребром и вместе не выбраны. Каждый дизъюнкт получил истинный литерал. $\blacksquare$

Обратите внимание, что доказательство не требует ничего, кроме внимательности. Такова и вся статья Карпа: двадцать одно рассуждение подобного рода, поставленных в правильном порядке.

Вопрос

Итог: либо все эти задачи решаются быстро, либо ни одна. Вопрос $\mathrm{P}$ против $\mathrm{NP}$ — «если решение легко проверить, легко ли его найти?» — вошёл в 2000 году в список семи задач тысячелетия и остаётся открытым.

Стоит понимать, что стоит на кону.

Если $\mathrm{P}=\mathrm{NP}$ и алгоритм практичен, вся современная криптография перестаёт работать — она вся построена на предположении, что перебор устранить нельзя. Но это меньшее из последствий. Проверка доказательства — тоже полиномиальная процедура; значит, при $\mathrm{P}=\mathrm{NP}$ всякую теорему с доказательством разумной длины можно было бы найти машинально. Математика в нынешнем виде кончилась бы.

Почти все специалисты считают, что $\mathrm{P}\neq\mathrm{NP}$. Доказательства нет, и известно, почему его трудно получить: два основных приёма теории вычислимости — релятивизация и естественные доказательства — доказано неприменимы к этому вопросу.

Письмо ГёделяКурт Гёдельавстрийский и американский логик · 1906–1978Доказал, что в любой достаточно богатой формальной системе есть истинные утверждения, которые она не может доказать, — и тем закрыл программу Гильберта в двадцать пять лет.

У задачи есть предыстория, о которой узнали только в 1988 году, когда в архиве нашли письмо.

20 марта 1956 года Курт Гёдель написал Джону фон НеймануДжон фон Нейманвенгеро-американский математик · 1903–1957Аксиоматизировал квантовую механику, основал теорию игр, придумал архитектуру компьютера и метод Монте-Карло — и всё это, по мнению современников, не напрягаясь.. Фон Нейман умирал от рака, и письмо было прощальным. В нём Гёдель спрашивал: пусть есть машина, которая по формуле и числу $n$ определяет, есть ли у формулы доказательство длины $n$. Перебор требует $2^{n}$ шагов. А что, если существует машина, справляющаяся за $n$ или $n^{2}$ шагов?

Дальше — фраза, в которой сформулировано всё: это имело бы «последствия величайшего значения», поскольку означало бы, что умственную работу математика при решении вопросов «да или нет» можно полностью заменить машиной.

Это вопрос $\mathrm{P}$ против $\mathrm{NP}$, заданный за пятнадцать лет до Кука и Карпа, в частном письме, которое никто не прочитал. Фон Нейман, вероятно, не успел ответить.

Круг замыкается и на нашей карте: вопрос Гёделя — прямое продолжение Entscheidungsproblem, а тот — программы Гильберта. Разница в одном: ГильбертДавид Гильбертнемецкий математик · 1862–1943Человек, сделавший Гёттинген столицей математики и задавший ей повестку на весь XX век — двадцатью тремя проблемами и одной программой, которую сам же и не смог спасти. спрашивал, есть ли алгоритм; Гёдель — сколько он стоит.

Задача. Докажите, что множество вершин $S$ независимо тогда и только тогда, когда $V\setminus S$ — вершинное покрытие. Что отсюда следует про задачи о наибольшем независимом множестве и наименьшем вершинном покрытии?
(Ответ: $S$ независимо $\iff$ ни одно ребро не лежит целиком внутри $S$ $\iff$ у каждого ребра хотя бы один конец вне $S$ $\iff$ $V\setminus S$ покрывает все рёбра. Значит, наибольшее независимое множество и наименьшее вершинное покрытие — дополнения друг друга, и любой алгоритм для одной задачи мгновенно даёт алгоритм для другой. Сравните с теоремой Кёнига: в двудольном графе наименьшее покрытие равно наибольшему паросочетанию и потому считается быстро — оговорка «двудольный» здесь стоит между полиномом и экспонентой.)

Следующая точка: Москва — где то же самое доказали независимо, напечатали на двух страницах и сформулировали удобнее.