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

• Название: Золотой билет. P, NP и границы возможного
• Автор: Лэнс Фотноу
• Жанр: Образовательная литература
• Год: 2016
• ISBN: 978-5-00101-424-9

«Золотой билет» – великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. В этой информативной и занимательной книге Лэнс Фортноу прослеживает работу, которая велась над задачей во времена холодной войны по обе стороны «железного занавеса», и приводит примеры ее возникновения во множестве дисциплин, включая экономику, физику и биологию.

Для студентов и специалистов в области теории вычислений, всех, интересующихся современными проблемами в математике.

В формате pdf A4 сохранен издательский дизайн.

---

Годом позже старшекурсники Университета Цинхуа в Пекине оптимизировали алгоритм Борова и запустили его на самом быстром компьютере в мире (который на тот момент находился в Китае). Меньше чем через неделю новый алгоритм разобрался со средней задачей о клике и решил несколько других типичных проблем из класса 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 погодный фактор не учитывала: ведь расписание составляют в декабре, на весь сезон вперед, а предсказать дождь настолько заранее просто невозможно. Вернее, было невозможно; но потом появился урбанский алгоритм.