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

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

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

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

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

---

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

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

Музыканты при помощи урбанского алгоритма дописывают знаменитые неоконченные классические произведения вроде «Турандот» Пуччини, Десятой симфонии Малера или Восьмой симфонии Шуберта («Неоконченной»), а также сочиняют новые, например – Десятую симфонию Бетховена. «Урбанская первая» – самая популярная симфония урбанского алгоритма – своим новаторским звуком привела концертную публику в настоящий восторг. Кое-кто создает даже композиции «Битлз» и Элвиса Пресли, синтезируя не только мелодию, но и голоса. Серьезные музыкальные критики утверждают, что это не искусство, поскольку элемент творчества здесь полностью отсутствует, однако люди все равно активно скачивают песни из сети.

Одни создают на компьютерах картины, другие – пьесы, романы и даже стихи… Какой-то киноман недавно сгенерировал романтическую комедию с молодыми Хамфри Богартом и Джулией Робертс, и зрители почти поверили, что актеры ради совместных съемок совершили путешествие во времени. Мечтаете увидеть «Волшебника из страны Оз» от Тима Бёртона? Так в чем проблема?

Amazon уже давно не рекомендует книги к прочтению. Теперь он может сделать для вас гораздо больше: индивидуальный роман, полностью отвечающий вашим вкусам и интересам, обойдется не дороже билета в кино. На канале NBC запустили многосерийное приключенческое «реалити-шоу» без актеров и сценаристов: каждая серия от начала и до конца генерируется компьютером. В последней версии приставки Xbox появилась игра, в которой ваша жизнь и мир вокруг создаются прямо на ходу. Сюжетные линии не предопределены заранее; игрок может действовать совершенно произвольно, а программа, не вмешиваясь, позволяет его действиям реализовываться. Из-за этого многие уже с трудом отделяют свою реальную (и не особо насыщенную) жизнь от виртуальной.

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

Первоклассный детектив

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

При расследовании массового убийства в Атланте, происшедшего уже в «пост-урбанский» период, полиции удалось получить образец ДНК с оставленной на месте преступления обертки от гамбургера. В национальной объединенной базе индексов ДНК – CODIS – соответствия не нашлось. Тогда один ученый из Технологического института Джорджии привлек к делу урбанский алгоритм. В результате был создан новый, натренированный на базе CODIS метод, способный по образцу ДНК определить не только физические параметры (рост, цвет глаз и кожи), но также черты характера, а иногда даже профессию. Сопоставив данные CODIS с фотографиями из полицейских досье, ученый вместе со студентами разработал алгоритм, который, обладая информацией о возрасте и наличии бороды и усов, рисовал по ДНК человека его примерный портрет.

В полиции попытались применить новый алгоритм для сопоставления ДНК с места преступления со снимками из уголовных дел. Поиск ничего не дал, и тогда алгоритм запустили на базе водительских прав. Через несколько часов подозреваемый Джордж Браун был уже под арестом. С преступлением его связывали лишь самые косвенные улики – отсутствие алиби и нарисованный компьютером портрет. Добровольно сдать образцы ДНК арестованный отказался, однако полиции удалось получить ордер; как и ожидалось, совпадение ДНК было полным. Джорджа Брауна признали виновным и приговорили к смертной казни.

Осужденный подал апелляцию. Адвокаты настаивали на том, что подобные методы расследования нарушают право на неприкосновенность частной жизни. Дело передали в Верховный суд США, который постановил, что использовать ДНК для установления личности правомерно. Ведь улику полиция получила законным путем, а затем над ней просто поработал некий алгоритм.

Несмотря на вердикт, дело вызвало волну общественного протеста. Неприкосновенность частной жизни находилась под угрозой. Тридцать восемь штатов на законодательном уровне запретили использовать образцы ДНК для каких-либо иных целей, кроме сличения с уже имеющимися в базе CODIS. А губернатор Джорджии в конечном итоге изменил Брауну меру пресечения на пожизненное заключение.

Обратная сторона медали

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

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

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

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

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