Равны ли P и NP?

Вопрос

Решать судоку можно долго, а проверить заполненную сетку — дело минуты. Найти множители огромного числа кажется безнадёжным, а проверить, что два данных числа дают его при умножении, тривиально. Для множества задач проверить ответ легко, а найти, похоже, трудно.

Вопрос в том, реальна ли эта разница или она лишь отражает нашу недостаточную изобретательность. На языке информатики P — класс задач, которые компьютер решает быстро, за время, растущее разумно, «полиномиально», с размером задачи. NP — класс задач, решения которых можно быстро проверить. Каждая задача из P входит в NP. Вопрос в том, верно ли обратное: любая ли задача, решение которой легко проверить, так же легко решается?

Что известно

Точно вопрос сформулировал в 1971 году Стивен Кук, а независимо от него — Леонид Левин в СССР. Курт Гёдель по сути задал тот же вопрос в письме Джону фон Нейману в 1956 году, но это письмо нашли лишь десятилетия спустя.
Кук показал, что в NP есть «самые трудные» задачи: к ним можно свести любую задачу из NP. В 1972 году Ричард Карп показал, что таковы 21 известная задача; их называют NP-полными. Сегодня их известны тысячи: составление расписаний, планирование маршрутов, упаковка, модели сворачивания белков и даже обобщённые версии игр вроде тетриса и судоку.
Они стоят или падают вместе. Быстрый алгоритм для любой одной NP-полной задачи дал бы быстрые алгоритмы для всего NP.
Большинство исследователей считают, что P ≠ NP. В опросе 2019 года так ответили почти девять из десяти специалистов по информатике.
Три известных «барьера» — релятивизация, естественные доказательства и алгебраизация — показывают, что целые семейства методов доказательства не могут решить вопрос. Успешное доказательство должно обойти все три.
Объявленные доказательства появляются регулярно, в обе стороны. Пока все они оказались ошибочными.

Основные гипотезы

P ≠ NP, и трудность реальна

Это мнение большинства. Десятилетия попыток тысяч очень способных людей найти быстрые алгоритмы для NP-полных задач провалились, и мир выглядит так, будто искать принципиально труднее, чем проверять. Но чтобы это доказать, нужно показать, что не может помочь никакой алгоритм, включая те, которых ещё никто не придумал. Это гораздо труднее, чем показать, что не работают известные алгоритмы.

P = NP, но бесполезно

Меньшинство, включая уважаемого информатика Дональда Кнута, считает P = NP возможным. Но даже тогда быстрый алгоритм может оказаться на практике настолько огромным, или его существование будет доказано без способа его построить, что в реальном мире ничего не изменится.

Независимость от аксиом

Некоторые думают, что вопрос вообще может быть неразрешим в рамках стандартной математики. Серьёзных свидетельств этому нет, но барьеры показывают, насколько необычным должно быть доказательство.

Где заканчивается понимание

Суть проблемы в том, что мы почти не умеем доказывать, что что-то трудно. Показать, что задача решается быстро, мы можем: достаточно предъявить алгоритм. Доказать, что быстрого алгоритма не существует, нам почти нечем. Для большинства естественных задач мы не можем исключить даже того, что они решаются за линейное время, то есть за простое чтение входных данных.

Второй пробел — между теорией и практикой. NP-полнота говорит о худшем случае, а программы, называемые SAT-решателями, регулярно решают промышленные экземпляры NP-полных задач с миллионами переменных. Мы до конца не понимаем, почему реальные экземпляры так часто оказываются лёгкими.

И есть разрыв между P ≠ NP и безопасностью. Современной криптографии нужны задачи, трудные в среднем, для случайно выбранных ключей, а не только в худшем случае. Доказательство P ≠ NP само по себе не доказало бы надёжность шифрования. А разложение на множители, основа RSA, даже не известно как NP-полная задача.

Что могло бы дать ответ

Доказательство P ≠ NP, которое почти наверняка потребует принципиально нового математического метода, проходящего все три барьера. На это нацелены программы вроде геометрической теории сложности, но их считают далёкими от цели на десятилетия.
Быстрый алгоритм для любой NP-полной задачи, который сразу доказал бы P = NP.
Доказательство того, что вопрос не зависит от стандартных аксиом математики.