| сформулировано | Стивен Кук · Леонид Левин · 1971 · независимо |
| статус | не решена · проблема тысячелетия · $1 000 000 |
| P | задачи, решаемые за полиномиальное время |
| NP | задачи, чьё решение проверяется за полиномиальное время |
| вопрос | P = NP ? |
| консенсус | большинство теоретиков считают P ≠ NP — но доказательства нет |
| следствие если P=NP | криптография сломана · ИИ переосмыслен · математика автоматизирована |
| связано | теорема Гёделя · теорема Тьюринга об остановке |
Вопрос, который ломает криптографию — если ответ не тот.
проверить решение судоку легко. найти его — сложно. всегда ли так? никто не знает.
Возьмите заполненный судоку. Чтобы проверить, что он правильный, нужно несколько секунд: убедиться, что в каждой строке, столбце и квадрате — все цифры от 1 до 9. А чтобы найти решение с нуля для пустого судоку 9×9, опытному человеку нужны минуты или часы. Это и есть разница между P и NP на интуитивном уровне.
Класс P — задачи, которые компьютер решает быстро: за время, ограниченное многочленом от размера входа. Сложение, сортировка, поиск кратчайшего пути в графе — всё это в P. Класс NP — задачи, для которых правильный ответ можно проверить быстро, даже если найти его трудно. Судоку, задача коммивояжёра, разложение целого числа на простые множители, проверка булевой формулы на выполнимость — всё это NP1.
Любая задача из P автоматически в NP — если можно решить за полиномиальное время, то и проверить тоже. Обратное — открытый вопрос. Существуют ли в NP задачи, которые принципиально нельзя решить быстро, или все они на самом деле тоже в P, а мы просто не нашли быстрых алгоритмов?
Если P = NP, то мир глубоко отличается от того, каким мы его представляем. — Скотт Ааронсон
Если P = NP, последствия трудно переоценить. Современная криптография — RSA, эллиптические кривые, хеши — основана на том, что некоторые NP-задачи (факторизация больших чисел, дискретный логарифм) вычислительно недоступны. P = NP означало бы, что они доступны — мы просто пока не знаем алгоритма. HTTPS, банковские транзакции, цифровые подписи — всё под угрозой переписывания.
С другой стороны: математика. Доказательство теоремы — это NP-задача (проверить доказательство легко, найти его — трудно). При P = NP можно было бы автоматически искать доказательства за разумное время. Большинство нерешённых проблем — гипотеза Римана, P vs NP сама — попали бы в зону досягаемости.
Если же P ≠ NP — это тоже нужно доказать. И вот этого никто не умеет2. Большинство специалистов считают, что P ≠ NP — это согласуется со всеми эмпирическими данными о вычислительной сложности. Но «большинство считает» — не аргумент в математике. До формального доказательства мы живём с открытым вопросом, который сидит в самой основе того, как устроены вычисления3.