За разницу между «найти» и «проверить» дают миллион долларов

Что именно сравнивают P и NP

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

Любую задачу из P можно быстро проверить: достаточно сначала быстро найти ответ, а затем убедиться, что он верен. Поэтому P входит в NP. Главный вопрос — совпадают ли эти классы: всегда ли быстрый способ проверки означает, что существует и быстрый способ решения?

Почему доказательство так трудно

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

Именно поэтому десятилетия попыток не завершились решением. Исследователи изучают отдельные классы алгоритмов и конкретные задачи, но такие результаты не обязательно охватывают весь набор возможных способов вычисления. Задача входит в число математических проблем тысячелетия; за её решение предусмотрена премия в миллион долларов.

Что изменится, если ответ найдут

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

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