Золотой билет. 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.

Глава 2. Совершенный мир

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

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

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

Урбанский алгоритм

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