Гипотезу Пуанкаре в 2003 году доказал Григорий Перельман, однако от вознаграждения ученый отказался. Остальные шесть задач тысячелетия на момент написания книги по-прежнему остаются открытыми.
Решите проблему "P против NP" – и получите настоящий золотой билет, т. е. миллион долларов США!
Лучше всего, конечно, если вы установите равенство P и NP: тогда у вас будет алгоритм для поиска всех золотых билетов (т. е. решения всех остальных задач из списка). Докажете, что P = NP, – получите шесть миллионов за решение шести задач тысячелетия. Впрочем, доказать как равенство, так и неравенство классов будет очень и очень непросто; если вам нужны шесть миллионов, вы скорее выиграете их в лотерею.
В поисках билета
Иногда найти билет все же удается. Предположим, мне нужно поехать из Чикаго в Нью-Йорк на машине. Не долго думая, я забиваю адрес в навигатор, который уже через минуту-другую показывает оптимальный маршрут, и жму на газ. Подробная карта США со всеми городами и улицами занимает миллионы байт; возможные маршруты исчисляются гораздо более крупными цифрами. Сколько маршрутов можно проложить из Чикаго в Нью-Йорк? Грубейший подсчет даст нам свыше вигинтиллиона (единица и 63 нуля) вариантов, и запрет движения по встречке на односторонних улицах мало что изменит. У навигатора просто нет времени на такое количество проверок; как же он умудряется найти самый быстрый маршрут?
На самом деле маршруты обладают одной интересной особенностью. Добавим в программу промежуточный пункт назначения – скажем, Питтсбург. Кратчайший маршрут из Чикаго в Нью-Йорк через Питтсбург – это сумма кратчайших маршрутов из Чикаго в Питтсбург и из Питтсбурга в Нью-Йорк. Без заезда в Питтсбург до Нью-Йорка можно добраться и быстрее, однако при наличии промежуточной точки наилучшим решением будет склеить два кратчайших маршрута.
Именно так и сужают круг поиска навигационные программы. Десять тысяч или даже сто тысяч вариантов – это уже не вигинтиллион; современный процессор проверит их без труда.
Поиск кратчайшего пути не охватывает все аспекты проблемы равенства P и NP. Задача коммивояжера доказывает, что при наличии огромного числа вариантов совсем не обязательно перебирать их все; главный вопрос, однако, заключается в том, всегда ли можно обойтись без такого перебора.
Долгая дорога
Эта книга расскажет вам захватывающую историю о P и NP. Что это за классы? Какая между ними разница? Что такое NP-полные, или самые трудные, поисковые задачи? Как они связаны с проблемой 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.
Глава 2. Совершенный мир
Представьте, что вас просят написать статью обо всех переменах, вызванных развитием интернета за последние двадцать лет. Вы ведь упомянете о компактном устройстве, которое лежит у вас в кармане и мгновенно предоставляет доступ к любой открытой информации? И о новом типе общения, сложившемся в социальных сетях? И о том, как трансформировалось кино и музыка? О нововведениях в работе издательств и новостных агентств? Изменений слишком много, и в одну статью их явно не вместить. А теперь вообразите, что сейчас начало девяностых и вы пишете статью, когда все это еще только предстоит…
Равенство P и NP будет означать, что у нас имеется универсальный эффективный алгоритм для всех NP-задач. Мир изменится настолько сильно, что развитие интернета превратится во второстепенный исторический факт. Описать сейчас подробно эти изменения или хотя бы предсказать основные последствия от внедрения новых технологий не представляется возможным.
Совершенный мир, в котором P = NP, вряд ли когда-нибудь станет реальностью. Однако заглянуть в него одним глазком мы все-таки можем. Представим наше общество через несколько лет после появления универсального эффективного алгоритма; перенесемся в далекий 2026-й и посмотрим для начала, как этот мир развивался.
Урбанский алгоритм
В 2016 году чешский математик Милена Павел послала по электронной почте письмо. Во вложении было описание универсального эффективного алгоритма для решения NP-задач. После долгих и тщательных проверок научное сообщество пришло к единому мнению: алгоритм работает, и проблема равенства P и NP наконец решена. Свою работу Милена скромно назвала "Об открытой проблеме Стивена Кука", а вот New York Times выпустила статью с громким и предельно кратким заголовком: "P = NP".
В 2018 году Милена Павел была удостоена Филдсовской премии. Эту престижную математическую награду впервые вручили женщине. Годом позже Математический институт Клэя выписал на имя Милены чек в один миллион долларов. Григорий Перельман был первым, кто решил одну из задач тысячелетия; Милена стала второй и в отличие от Перельмана свой приз забрала. Часть денег (точные цифры не раскрываются) она пожертвовала на учреждение стипендий в своем родном университете в Праге.
В теории алгоритм Милены стал настоящим прорывом; в реальности же он работал слишком долго и потому оказался совершенно неприменим. В 2017 году российский ученый Михаил Боров придумал интересную модификацию и ускорил алгоритм на порядок, однако до практического применения по-прежнему было очень и очень далеко.
Годом позже старшекурсники Университета Цинхуа в Пекине оптимизировали алгоритм Борова и запустили его на самом быстром компьютере в мире (который на тот момент находился в Китае). Меньше чем через неделю новый алгоритм разобрался со средней задачей о клике и решил несколько других типичных проблем из класса NP. Ряд промышленных гигантов, среди которых были Boeing и Daimler-Benz, заключили с университетом контракт на разработку решения особо хитрых оптимизационных задач. В результате новое воздушное судно "Боинг-797" получило крыло улучшенной конструкции, а вместе с ним и возможность летать из Лондона в Сидней без остановок.
Среди прочих над проектом работал аспирант Иллинойского университета в Урбане Стивен Франк, проходивший в то время в Пекине семестровую стажировку. Вернувшись в родную Урбану, Стивен пожаловался научному руководителю, что, несмотря на все их ухищрения, на решение одной-единственной и далеко не самой сложной NP-задачи все равно уходит как минимум несколько дней.
"Когда джинн обещает выполнить одно – и только одно – твое желание, что нужно попросить?" – спросил ученый.
"Не знаю", – растерялся Стивен.
"Другого джинна, который выполнит все твои желания!"
На Стивена снизошло озарение. Он, конечно, знал, что для задачи о клике существуют и более совершенные алгоритмы, однако своими силами найти их не мог; зато у него был знакомый джинн (программа из университета Цинхуа), способный относительно быстро перебрать экспоненциальное число потенциальных вариантов. Стивен написал программу, которая работала аналогично цинхуанской и искала наилучший алгоритм решения NP-задач. А затем получил разрешение на использование вычислительных ресурсов Национального суперкомпьютерного центра (NCSA) в Иллинойском университете. Прошло несколько недель, и усилия Стивена наконец увенчались успехом: найденный программой алгоритм был на пять процентов быстрее цинхуанского. Неплохой результат для научной статьи; однако ни о каком прорыве речи пока не шло.
"Давай еще раз – с новым алгоритмом", – подсказал научный руководитель.
Стивен запустил новую программу, чтобы та нашла еще более быстрый алгоритм; через несколько недель ускорение было уже двадцатипроцентным.
"Продолжай", – лаконично отреагировал научный руководитель. Казалось, он совсем не удивлен.
"Пора уже мне это автоматизировать. Пусть он сам запускает новый поиск всякий раз, как найдет очередной алгоритм!" – проворчал Стивен.
"Слава тебе, Господи, дошло наконец!" – читалось во взгляде научного руководителя.
Вернувшись в лабораторию, Стивен взялся за программу, которая должна была находить самый быстрый алгоритм, создавать на его основе новую программу, находить еще более быстрый алгоритм, и так далее – до тех пор, пока алгоритмы не перестанут улучшаться.
"Ты не боишься, что будет как со Скайнетом?" – поинтересовался коллега.
"С чем – с чем?"
"Ну, когда компьютер становится чересчур умным, он обретает сознание и захватывает мир, как Скайнет в "Терминаторе"".
"Ты серьезно? Это же просто программа! Не волнуйся, все будет хорошо!"
И вот Стивен снова запустил свой код на вычислительном гиганте NSCA. С каждым шагом алгоритмы становились все лучше и лучше. Наконец, процесс остановился; окончательный вариант программы состоял из 42 миллионов строк безличного машинного кода. Удивительно, но этот код решал NP-задачи очень быстро и при этом не пытался обрести сознание и захватить наш мир. Университетский пресс-релиз на все лады расхваливал новый "урбанский алгоритм"; название прижилось, и других вариантов уже никто не предлагал.
Некоторые университетские математики, раньше других получившие доступ к урбанскому алгоритму, пытались доказать с его помощью остальные проблемы тысячелетия. Рассуждения у них по большей части были довольно невразумительные; впрочем, Математический институт Клэя вовремя сориентировался и выпустил официальное заявление: никакие новые доказательства, полученные в результате тех или иных модификаций алгоритма Милены Павел, который уже принес своей создательнице награду в миллион долларов, рассматриваться не будут.
Многие фирмы желали выкупить права на урбанский алгоритм или хотя бы приобрести временную лицензию на его использование. Все они прочно увязли в юридическом болоте, поскольку владельцами алгоритма считали себя практически все кому не лень. Помимо Стивена Франка и его научного руководителя права на алгоритм заявили также центр NSCA и чешское правительство, спонсировавшее исследования Милены. Сознавая всю важность полученных Стивеном результатов, Всемирная торговая организация постановила, что урбанский алгоритм не является объектом авторского права и после выплаты некоторой компенсации его создателям должен сделаться всеобщим достоянием; размер компенсации установит специальная комиссия. Против высказались одни лишь китайцы, однако было ясно, что заблокировать решение ВТО они не смогут. Наконец, 23 октября 2019 года урбанский алгоритм стал общедоступным.
И тогда наш мир начал меняться…
Компьютеры – рак – 1: 0
Вернувшись в кабинет, лечащий врач Хелен плотно закрыл дверь.
"Боюсь, новости у меня не очень хорошие, – начал он. – У вас рак печени".
"Откуда вы знаете? – задохнулась Хелен. Ей всего сорок два; у нее муж и дети, трое ребят от шести до пятнадцати. – Я ведь только кровь сдавала!"
"Когда есть образцы ДНК, по маркерам в крови можно выявить не только наличие рака, но даже его тип и стадию. Хотите – сделаем биопсию. Хотя анализы крови теперь настолько точны, что необходимость в этой небезопасной процедуре практически отпала".
"У моей двоюродной сестры тоже нашли рак печени. Восемь лет назад, в 2018-м. Вариантов лечения тогда было немного. Через семь месяцев ее не стало…"
"За десять лет многое изменилось! Унифицированные методы лечения мало что давали. Со временем стало ясно, что подход должен быть строго индивидуальным. Сначала мы анализируем образцы ДНК здоровых и мутировавших раковых клеток пациента, а затем создаем протеины, заставляя их сворачиваться так, чтобы эффективно нейтрализовывать раковые клетки и не причинять никакого вреда здоровым. Мертвые раковые клетки сами постепенно выводятся из организма".
"Наверно, это стоит кучу денег…" – задумчиво протянула Хелен.
"Кучу денег стоила химиотерапия! Новый метод обойдется вам всего в две тысячи, и со временем он будет становиться все дешевле и дешевле. Ваша страховка покроет почти все расходы".
"Фантастика! Но что же такого случилось за последние десять лет? Почему лечить и делать анализы теперь настолько просто?"
"Исследования на эту тему велись уже давно, однако существенно продвинуться в расшифровке ДНК не позволяли даже самые мощные компьютеры. С появлением урбанского алгоритма все изменилось; за несколько лет нам удалось добиться невероятного прогресса. Обычно новые методы тестируются годами, но в этот раз первые же испытания прошли с ошеломляющим успехом, так что Министерство здравоохранения посчитало нечестным лишать людей такой возможности".
"Понятно. Тогда давайте начнем!"
"Начнем что? Кровь мы у вас уже взяли, анализ сделали. Вот рецепт, – ответил доктор, протягивая Хелен флешку вместо привычного листка бумаги. – Здесь записаны коды белков, которые вам нужны. Отнесите это в аптеку, и они вам сделают таблетки. За две недели все раковые клетки будут выведены из организма. И никаких побочных эффектов! Но имейте ввиду, что рецепт подходит только вам. ДНК у все разная; если таблетки выпьет кто-то еще, последствия могут быть очень и очень серьезными".
"Поверить не могу… Меня не будет тошнить, и волосы не выпадут? Если рак диагностируют на ранней стадии, можно просто выпить таблетку – и он пройдет, как обычная простуда? И все благодаря какому-то алгоритму?!"
"Ну… не совсем. Алгоритм, конечно, очень помог в лечении рака, СПИДа, диабета, но вот обычная простуда до сих пор остается для медиков загадкой".
Пост-урбанский бейсбол
"Отличный денек, как раз для бейсбола!" – приговаривал Рэнди, пока они с его двенадцатилетней дочерью Кейт ехали в Сент-Луис на ее первую в жизни бейсбольную игру – и последнюю в сезоне 2026 года. "Сент-Луис Кардиналс" принимали у себя "Милуоки Брюэрс"; предстояла жесткая борьба за чемпионский титул. Рэнди размышлял о том, как сильно изменилась игра со времен его детства – особенно в последние годы, когда на сцену вышел урбанский алгоритм. Удивительно: ведь технически бейсбол настолько прост, что в нем даже часы не нужны.
Первые реформы коснулись, конечно же, расписания. В далеком 2004-м расписание для Главной бейсбольной лиги составлял супружеский тандем – Генри и Холли Стефенсон. Условия были предельно просты; как правило, учитывалось лишь количество выездных и домашних игр да еще некоторые особые пожелания (к примеру, в День патриота в середине апреля "Ред Сокс" хотели провести дневную игру на своем поле в Бостоне, поскольку недалеко от стадиона как раз пробегали бостонские марафонцы). В 2005-м лига заключила контракт с питтсбургской компанией Sports Scheduling Group, у которой одни и те же команды почти никогда не встречались друг с другом две недели подряд. Как известно, под ливнем в бейсбол на улице не поиграешь, однако Sports Scheduling Group погодный фактор не учитывала: ведь расписание составляют в декабре, на весь сезон вперед, а предсказать дождь настолько заранее просто невозможно. Вернее, было невозможно; но потом появился урбанский алгоритм.
Метеорология вышла на совершенно новый уровень. Предсказать температуру, ветер, облачность, осадки можно было очень точно и почти на год вперед. Конечно, современные алгоритмы тоже справляются довольно неплохо – предвидят ураганы, штормы, торнадо и землетрясения, давая людям возможность подготовиться и даже куда-то уехать. Но они работают как скорая помощь, а урбанский алгоритм полностью изменил весь наш быт. Школы заблаговременно вносят в расписание снегопад. Пастор, проводящий церемонию бракосочетания на воздухе, поднимает цены в хорошую погоду и делает скидки тем, кто согласен на дождь, жару и влажность. Людям нравится смотреть игру в ясный, теплый день; есть ли смысл торчать в дождливом или облачном Детройте, когда в Миннеаполисе вовсю сверкает солнце и простаивает стадион?