Золотой билет. P, NP и границы возможного

На Стивена снизошло озарение. Он, конечно, знал, что для задачи о клике существуют и более совершенные алгоритмы, однако своими силами найти их не мог; зато у него был знакомый джинн (программа из университета Цинхуа), способный относительно быстро перебрать экспоненциальное число потенциальных вариантов. Стивен написал программу, которая работала аналогично цинхуанской и искала наилучший алгоритм решения NP-задач. А затем получил разрешение на использование вычислительных ресурсов Национального суперкомпьютерного центра (NCSA) в Иллинойском университете. Прошло несколько недель, и усилия Стивена наконец увенчались успехом: найденный программой алгоритм был на пять процентов быстрее цинхуанского. Неплохой результат для научной статьи; однако ни о каком прорыве речи пока не шло.

«Давай еще раз – с новым алгоритмом», – подсказал научный руководитель.

Стивен запустил новую программу, чтобы та нашла еще более быстрый алгоритм; через несколько недель ускорение было уже двадцатипроцентным.

«Продолжай», – лаконично отреагировал научный руководитель. Казалось, он совсем не удивлен.

«Пора уже мне это автоматизировать. Пусть он сам запускает новый поиск всякий раз, как найдет очередной алгоритм!» – проворчал Стивен.

«Слава тебе, Господи, дошло наконец!» – читалось во взгляде научного руководителя.

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

«Ты не боишься, что будет как со Скайнетом?» – поинтересовался коллега.

«С чем – с чем?»

«Ну, когда компьютер становится чересчур умным, он обретает сознание и захватывает мир, как Скайнет в „Терминаторе“».

«Ты серьезно? Это же просто программа! Не волнуйся, все будет хорошо!»

И вот Стивен снова запустил свой код на вычислительном гиганте NSCA. С каждым шагом алгоритмы становились все лучше и лучше. Наконец, процесс остановился; окончательный вариант программы состоял из 42 миллионов строк безличного машинного кода. Удивительно, но этот код решал NP-задачи очень быстро и при этом не пытался обрести сознание и захватить наш мир. Университетский пресс-релиз на все лады расхваливал новый «урбанский алгоритм»; название прижилось, и других вариантов уже никто не предлагал.

Некоторые университетские математики, раньше других получившие доступ к урбанскому алгоритму, пытались доказать с его помощью остальные проблемы тысячелетия. Рассуждения у них по большей части были довольно невразумительные; впрочем, Математический институт Клэя вовремя сориентировался и выпустил официальное заявление: никакие новые доказательства, полученные в результате тех или иных модификаций алгоритма Милены Павел, который уже принес своей создательнице награду в миллион долларов, рассматриваться не будут.

Многие фирмы желали выкупить права на урбанский алгоритм или хотя бы приобрести временную лицензию на его использование. Все они прочно увязли в юридическом болоте, поскольку владельцами алгоритма считали себя практически все кому не лень. Помимо Стивена Франка и его научного руководителя права на алгоритм заявили также центр NSCA и чешское правительство, спонсировавшее исследования Милены. Сознавая всю важность полученных Стивеном результатов, Всемирная торговая организация постановила, что урбанский алгоритм не является объектом авторского права и после выплаты некоторой компенсации его создателям должен сделаться всеобщим достоянием; размер компенсации установит специальная комиссия. Против высказались одни лишь китайцы, однако было ясно, что заблокировать решение ВТО они не смогут. Наконец, 23 октября 2019 года урбанский алгоритм стал общедоступным.

И тогда наш мир начал меняться…

Компьютеры – рак – 1: 0

Вернувшись в кабинет, лечащий врач Хелен плотно закрыл дверь.

«Боюсь, новости у меня не очень хорошие, – начал он. – У вас рак печени».

«Откуда вы знаете? – задохнулась Хелен. Ей всего сорок два; у нее муж и дети, трое ребят от шести до пятнадцати. – Я ведь только кровь сдавала!»

«Когда есть образцы ДНК, по маркерам в крови можно выявить не только наличие рака, но даже его тип и стадию. Хотите – сделаем биопсию. Хотя анализы крови теперь настолько точны, что необходимость в этой небезопасной процедуре практически отпала».

«У моей двоюродной сестры тоже нашли рак печени. Восемь лет назад, в 2018-м. Вариантов лечения тогда было немного. Через семь месяцев ее не стало…»

«За десять лет многое изменилось! Унифицированные методы лечения мало что давали. Со временем стало ясно, что подход должен быть строго индивидуальным. Сначала мы анализируем образцы ДНК здоровых и мутировавших раковых клеток пациента, а затем создаем протеины, заставляя их сворачиваться так, чтобы эффективно нейтрализовывать раковые клетки и не причинять никакого вреда здоровым. Мертвые раковые клетки сами постепенно выводятся из организма».

«Наверно, это стоит кучу денег…» – задумчиво протянула Хелен.