Лэнс Фотноу - Золотой билет. P, NP и границы возможного

Для наглядности приведу один маленький пример. Сколько человек входит в максимальную клику на Facebook , т. е. в наибольшую по численности группу, в которой все дружны между собой? Может, сотня? А может быть, тысяча? Даже при наличии доступа ко всем необходимым данным ответить на этот вопрос будет крайне непросто; искать максимальную клику не легче, чем возиться с какой-нибудь другой поисковой проблемой.

Какая перспектива ожидает нас, если классы равны? Совершенный мир, в котором все можно вычислить быстро. Ответы на вопросы будут приходить почти мгновенно; смертельных болезней не останется, и вселенная раскроет нам все свои тайны. Однако есть здесь и своя ложка дегтя: с компьютерами, которые могут почти все, нас ждет безработица и потеря конфиденциальности.

Впрочем, жизнь в совершенном мире нам, скорее всего, не грозит. Так что трудные поисковые задачи никуда от нас не денутся. Впрочем, это еще не повод опускать руки: для таких задач разработаны особые методы. Эвристические алгоритмы, к примеру, почти во всех случаях выдают корректный ответ, а приближенные позволяют получить решение, близкое к оптимальному.

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

С какой стороны зайти, чтобы вывести неравенство P ≠ NP? Курт Гёдель показал, что не у всех математических проблем имеется решение; возможно, аналогичным образом удастся доказать тот факт, что не для всех поисковых задач существует быстрый алгоритм. Еще вариант – попытаться разделить вычислительный процесс на более мелкие части, чтобы сложность исходной задачи было легче оценить. Некоторую надежду дает также алгебраическая геометрия – молодой и абсолютно абстрактный раздел математики. Впрочем, до решения проблемы мы в любом случае дойдем еще очень не скоро.

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

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

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

Упомянутые ранее тридцать восемь чисел

14175, 15055, 16616, 17495, 18072, 19390, 19731, 22161, 23320, 23717, 26343, 28725, 29127, 32257, 40020, 41867, 43155, 46298, 56734, 57176, 58306, 61848, 65825, 66042, 68634, 69189, 72936, 74287, 74537, 81942, 82027, 82623, 82802, 82988, 90467, 97042, 97507, 99564

можно разбить на две равные группы следующим образом:

15055, 16616, 19390, 22161, 26343, 40020, 41867, 43155, 46298, 57176, 58306, 65825, 66042, 69189, 74537, 81942, 82623, 82988, 90467

и 14175, 17495, 18072, 19731, 23320, 23717, 28725, 29127, 32257, 56734, 61848, 68634, 72936, 74287, 82027, 82802, 97042, 97507, 99564.

Числа каждой группы дают в сумме ровно 1000000.

Представьте, что вас просят написать статью обо всех переменах, вызванных развитием интернета за последние двадцать лет. Вы ведь упомянете о компактном устройстве, которое лежит у вас в кармане и мгновенно предоставляет доступ к любой открытой информации? И о новом типе общения, сложившемся в социальных сетях? И о том, как трансформировалось кино и музыка? О нововведениях в работе издательств и новостных агентств? Изменений слишком много, и в одну статью их явно не вместить. А теперь вообразите, что сейчас начало девяностых и вы пишете статью, когда все это еще только предстоит…

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

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

В 2016 году чешский математик Милена Павел послала по электронной почте письмо. Во вложении было описание универсального эффективного алгоритма для решения NP-задач. После долгих и тщательных проверок научное сообщество пришло к единому мнению: алгоритм работает, и проблема равенства P и NP наконец решена. Свою работу Милена скромно назвала «Об открытой проблеме Стивена Кука», а вот New York Times выпустила статью с громким и предельно кратким заголовком: «P = NP».

В 2018 году Милена Павел была удостоена Филдсовской премии. Эту престижную математическую награду впервые вручили женщине. Годом позже Математический институт Клэя выписал на имя Милены чек в один миллион долларов. Григорий Перельман был первым, кто решил одну из задач тысячелетия; Милена стала второй и в отличие от Перельмана свой приз забрала. Часть денег (точные цифры не раскрываются) она пожертвовала на учреждение стипендий в своем родном университете в Праге.

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

Годом позже старшекурсники Университета Цинхуа в Пекине оптимизировали алгоритм Борова и запустили его на самом быстром компьютере в мире (который на тот момент находился в Китае). Меньше чем через неделю новый алгоритм разобрался со средней задачей о клике и решил несколько других типичных проблем из класса NP. Ряд промышленных гигантов, среди которых были Boeing и Daimler-Benz , заключили с университетом контракт на разработку решения особо хитрых оптимизационных задач. В результате новое воздушное судно «Боинг-797» получило крыло улучшенной конструкции, а вместе с ним и возможность летать из Лондона в Сидней без остановок.