Золотой билет. 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.
Глава 2. Совершенный мир
Представьте, что вас просят написать статью обо всех переменах, вызванных развитием интернета за последние двадцать лет. Вы ведь упомянете о компактном устройстве, которое лежит у вас в кармане и мгновенно предоставляет доступ к любой открытой информации? И о новом типе общения, сложившемся в социальных сетях? И о том, как трансформировалось кино и музыка? О нововведениях в работе издательств и новостных агентств? Изменений слишком много, и в одну статью их явно не вместить. А теперь вообразите, что сейчас начало девяностых и вы пишете статью, когда все это еще только предстоит…
Равенство P и NP будет означать, что у нас имеется универсальный эффективный алгоритм для всех NP-задач. Мир изменится настолько сильно, что развитие интернета превратится во второстепенный исторический факт. Описать сейчас подробно эти изменения или хотя бы предсказать основные последствия от внедрения новых технологий не представляется возможным.
Совершенный мир, в котором P = NP, вряд ли когда-нибудь станет реальностью. Однако заглянуть в него одним глазком мы все-таки можем. Представим наше общество через несколько лет после появления универсального эффективного алгоритма; перенесемся в далекий 2026-й и посмотрим для начала, как этот мир развивался.
Урбанский алгоритм
В 2016 году чешский математик Милена Павел послала по электронной почте письмо. Во вложении было описание универсального эффективного алгоритма для решения NP-задач. После долгих и тщательных проверок научное сообщество пришло к единому мнению: алгоритм работает, и проблема равенства P и NP наконец решена. Свою работу Милена скромно назвала «Об открытой проблеме Стивена Кука», а вот New York Times выпустила статью с громким и предельно кратким заголовком: «P = NP».
В 2018 году Милена Павел была удостоена Филдсовской премии. Эту престижную математическую награду впервые вручили женщине. Годом позже Математический институт Клэя выписал на имя Милены чек в один миллион долларов. Григорий Перельман был первым, кто решил одну из задач тысячелетия; Милена стала второй и в отличие от Перельмана свой приз забрала. Часть денег (точные цифры не раскрываются) она пожертвовала на учреждение стипендий в своем родном университете в Праге.
В теории алгоритм Милены стал настоящим прорывом; в реальности же он работал слишком долго и потому оказался совершенно неприменим. В 2017 году российский ученый Михаил Боров придумал интересную модификацию и ускорил алгоритм на порядок, однако до практического применения по-прежнему было очень и очень далеко.
Годом