Лэнс Фортноу

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


Скачать книгу

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

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

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

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

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

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

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

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

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

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

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

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

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

      Компьютеры