Мадху Судан | Проблема P и NP: экзистенциальный вопрос математики

Лекция по проблемам Премии тысячелетия, 03.12.2025

Докладчик: Мадху Судан, Гарвардский университет

Название: Проблема P против NP: экзистенциальный вопрос математики

Аннотация: В начале XX века, в ответ на вопросы, поднятые Гильбертом, такие выдающиеся математики, как Гёдель, Чёрч и Тьюринг, формализовали понятия теорем и доказательств. Доказательства автоматически проверяются, в то время как теоремы представляют собой логические суждения, для которых существуют доказательства. Формальное определение компьютера, оказавшее сильное влияние на последующее развитие технологий, стало побочным продуктом усилий по определению понятия «автоматически проверяемый»!

Хотя получившаяся теория уже имела важные последствия, в ранних определениях, однако, отсутствовало одно понятие. Доказательства должны были быть легко проверяемыми, в то время как определение истинности суждения/гипотезы (возможно, основная задача математики) не обязательно было таковым. Но что такое «лёгкость» и как её определить? Хотя на это намекал уже Гёдель в 50-х годах, это понятие было окончательно формализовано в основополагающих работах Кука, Левина и Карпа в начале 70-х годов. Ключевыми моментами здесь стали принятие представления о том, что полиномиальные алгоритмы являются (единственными) разрешимыми, и понимание того, что алгоритмы, стремящиеся удалить квантор существования из определения «теоремы», наивно приводят к алгоритмам с экспоненциальным временем. Но разве нет сложных алгоритмов для поиска доказательств? Это и есть основополагающий вопрос: «P = NP?».

В этом докладе мы познакомимся с этим вопросом и объясним последствия его решения для современной вычислительной инфраструктуры, математики и других наук. Мы кратко опишем состояние дел в этой области и недавние успехи в более слабых её вариантах. Наконец, мы также постараемся связать этот вопрос, а также выяснить, почему можно полагать, что P != NP (поиск доказательства не может быть автоматизирован) даже несмотря на накапливающиеся доказательства способности компьютеров решать все более сложные математические задачи, которые, как кажется, реализуют поиск методом прямого перебора менее чем за полиномиальное время.