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

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

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

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

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

---

Метеорология вышла на совершенно новый уровень. Предсказать температуру, ветер, облачность, осадки можно было очень точно и почти на год вперед. Конечно, современные алгоритмы тоже справляются довольно неплохо – предвидят ураганы, штормы, торнадо и землетрясения, давая людям возможность подготовиться и даже куда-то уехать. Но они работают как скорая помощь, а урбанский алгоритм полностью изменил весь наш быт. Школы заблаговременно вносят в расписание снегопад. Пастор, проводящий церемонию бракосочетания на воздухе, поднимает цены в хорошую погоду и делает скидки тем, кто согласен на дождь, жару и влажность. Людям нравится смотреть игру в ясный, теплый день; есть ли смысл торчать в дождливом или облачном Детройте, когда в Миннеаполисе вовсю сверкает солнце и простаивает стадион?

В конце сезона зритель хочет видеть только значимые игры. Биться должны лучшие – с этим согласны и завсегдатаи стадионов, и «домашние» болельщики. Когда Рэнди был ребенком, предсказать успех команды мог разве что экстрасенс; теперь же научные методы с пугающей точностью определяют, кто в сентябре поборется за чемпионский титул. Конечно, такие методы не всегда предсказывают чемпионство: фактор случайности никто не отменял, и за сезон происходит несколько незапланированных поражений. Впрочем, это от них и не требуется: главное – заполнить верхние строчки турнирной таблицы. Каждый год объявляются очередные будущие аутсайдеры; каждый год оскорбленные болельщики кричат, что компьютер промахнулся. Но компьютер не промахивается. Никогда. За исключением одного-единственного (сильно нашумевшего) раза.

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

Итак, в прекрасный ясный день Рэнди ведет дочь на матч. «Кардиналс», естественно, взимают за погоду дополнительные сборы, но за хороший сервис Рэнди не прочь и приплатить.

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

Рэнди с дочерью усаживаются на свои места. Оглядев стадион, Рэнди замечает пустую площадку: раньше здесь всегда находился оператор с огромной телевизионной камерой. Теперь камер стало двадцать; они очень маленькие, едва различимые глазом, и расположены по всему периметру стадиона. Программа, разработанная на основе урбанского алгоритма, собирает с них данные и тут же формирует детальную трехмерную модель. По этой модели компьютер может создать видео, в котором игра будет показана со всех точек поля и во всех направлениях. Зритель увидит питчера глазами кэтчера и узнает, что проносится перед глазами бегущего на третью базу. Формально все изображения генерируются компьютером, однако выглядят они совсем как настоящие. Участникам одного известного эксперимента показывали реальное, снятое на камеру видео вперемешку с компьютерным; 89 из 100 подумали, что компьютерное изображение как раз и есть реальное.

Телевизоры нового поколения уже умеют работать непосредственно с трехмерными моделями; по ходу игры зритель может виртуально переместиться в любое место поля.

В момент удара битой по мячу компьютер точно рассчитывает его будущую траекторию, а затем безошибочно определяет наилучшее место для съемки. Трансляцию теперь обслуживают всего четыре человека: два комментатора, продюсер и техник – так, на всякий случай. Впрочем, технические проблемы во время игры возникают крайне редко. За этим матчем пристально следят и в Токио: у «Сент-Луиса», так же как и у «Милуоки», в составе есть известный японский бейсболист. Репортаж, по обыкновению, ведется на английском, однако в Японии зрители слышат родной язык. Комментаторы все те же, вот только созданные на основе урбанского алгоритма программы распознают их голоса и после автоматического перевода синтезируют безукоризненную японскую речь. Трансляция доступна на 876 языках и диалектах мира.

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

Виртуальный спорт перешел на совершенно новый уровень. В вымышленном матче теперь можно объединить игроков из разных команд или даже эпох. Питчер Сай Янг будет подавать на Джо ди Маджо, оба в расцвете спортивной карьеры; «Янкиз» 1927-го года сыграют против «Янкиз» 1998-го… Отделить реальный мир от виртуального стало очень трудно. Однажды программист со спортивного канала ESPN устроил первоапрельский розыгрыш и изменил в программе одну небольшую деталь. В результате зрители в прямом эфире наблюдали, как его любимая баскетбольная команда «Бостон Селтикс» побеждает «Нью-Йорк Никс», хотя в реальности все обстояло в точности наоборот. После той трансляции полетели многие головы…

С обязанностями судьи компьютеры тоже справляются на «отлично». Они не ошибаются и с удивительной точностью определяют все ауты, болы, страйки и хоумраны. Колледжи и низшая лига в целях экономии пользуются только электронными арбитрами; Главная лига настаивает, что судья должен быть «настоящим». Дискуссия на эту тему возникает всякий раз, когда очередная судейская ошибка влияет на исход игры.

После инцидента на Мировой серии 2022 года Главная лига бейсбола запретила использование любых электронных устройств на протяжении всего матча, опасаясь (и вполне справедливо), что компьютеры скоро отнимут работу у бейсбольных менеджеров. «Для нашего общего блага», – заявили в пресс-службе.

Потягивая холодное пиво и закусывая хот-догом (и то и другое отличного качества и при этом полезно для здоровья – благодаря новым рецептам, созданным при помощи урбанского алгоритма), Рэнди наслаждается игрой вживую – прямо как в старые времена, когда он был ребенком. Конечно, можно было бы сэкономить и посмотреть игру по телевизору – с прекрасными ракурсами, и к тому же в 3D-режиме. С новыми технологиями домашний просмотр дает гораздо больше впечатлений, чем поход на стадион; однако Рэнди нравится ощущать себя частью происходящего, а создать подобный эмоциональный настрой не под силу даже урбанскому алгоритму.

Турнирную таблицу можно скачать в интернете, но Рэнди учит Кэйт заполнять ее самостоятельно – так же, как учил его в свое время отец. Почти все вокруг изменилось под влиянием новых технологий, и в особенности – с появлением урбанского алгоритма, однако правила игры остаются все те же. Три страйка – и бьющий выбывает из игры. Всегда.

Бритва Оккама

Урбанский алгоритм перенес нас в мир, где любая болезнь поддается лечению, метеорологи всегда дают точный прогноз, а компьютерная реальность неотличима от настоящей. Как такое возможно? Ведь это всего лишь программа, пусть даже и очень умная… В поисках ответа мы отправимся в самое начало XIV века.

Уильям Оккам (или, точнее, Оккамский) еще юношей вступил во Францисканский орден. В XIV веке в Оксфорде наряду с францисканцами базировался также целый ряд других религиозных орденов; все они давали кров студентам Оксфордского университета, среди которых был и изучавший теологию Уильям. Университет он так и не закончил, однако это не помешало ему стать одним из величайших мыслителей Средневековья и внести поистине неоценимый вклад в физику, теологию, логику и философию. Широкой публике Оккам известен в основном благодаря своему принципу «бритва Оккама», согласно которому лучшим объяснением следует считать самое простое. Почему бритва? Вероятнее всего, потому, что она позволяет «сбривать», т. е. отсекать, все ненужное, оставляя лишь самую простую часть – и неважно, о каком предмете идет речь. Для науки и философии этот принцип стал основополагающим еще в эпоху Возрождения и продолжает оставаться таковым и сейчас.