Проблема P против NP

Проблема P против NP ставит вопрос о том, может ли каждая задача, решения которой можно быстро проверить, быть также быстро решена. Это центральный открытый вопрос теоретической информатики и одна из проблем тысячелетия Института Клэя.

Definition

P — это класс задач, разрешимых за полиномиальное время, а NP — класс задач, предлагаемые решения которых проверяемы за полиномиальное время; проблема P против NP ставит вопрос о равенстве этих двух классов, что имеет место тогда и только тогда, когда некоторая NP-полная задача разрешима за полиномиальное время.

Scope

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

Core questions

• Является ли нахождение решения принципиально более сложным, чем его проверка?
• Почему ответ зависит от того, принадлежит ли какая-либо одна NP-полная задача классу P?
• Как бы выглядел мир, если бы P равнялось NP, и если бы не равнялось?
• Почему десятилетия усилий не привели к разрешению этого вопроса?

Key theories

Эквивалентность NP-полноте

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

Барьеры доказательства

Результаты по релятивизации, естественным доказательствам и алгебраизации показывают, что основные известные методы доказательства не могут решить проблему P против NP, что объясняет трудность и направляет поиск принципиально новых методов.

Clinical relevance

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

History

Кук сформулировал этот вопрос в 1971 году наряду с NP-полнотой, и он быстро был признан фундаментальным. Попытки, предпринятые в 1980-х годах с использованием нижних оценок сложности схем, столкнулись с барьером естественных доказательств, выявленным Разборовым и Рудичем, а в 2000 году Математический институт Клэя назвал её проблемой тысячелетия с призом в один миллион долларов.

Debates

Будет ли когда-либо решена проблема P против NP, и каков будет ответ?

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

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp
• Alexander Razborov

Seminal works

• cook1971
• aroraBarak2009

Frequently asked questions

Что произойдет, если P будет равно NP?

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

Почему эту проблему так сложно решить?

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