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

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

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

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

Французский мыслитель XVII века Рене Декарт пользовался «бритвой Оккама» для доказательства существования окружающего мира. Самое известное изречение ученого – это, безусловно, Cogito ergo sum, или «Я мыслю, следовательно, я существую». В философском трактате «Рассуждение о методе» Декарт выводит факт своего существования практически из ничего, основываясь лишь на своей способности рассуждать о себе. А как обстоит дело с внешним миром? Может, все, что окружает Декарта, существует лишь в его сознании? Ученый отвергает эту идею, выдвигая более простое и к тому же более вероятное объяснение: все люди – так же как и он сам – живут в реальном физическом мире, который можно исследовать и пытаться понять.

«И, заметив, что в истине положения „Я мыслю, следовательно, я существую“ меня убеждает единственно ясное представление, что для мышления надо существовать, я заключил, что можно взять за общее правило следующее: все представляемое нами вполне ясно и отчетливо – истинно. Однако некоторая трудность заключается в правильном различении того, что именно мы способны представлять себе вполне отчетливо».

Рене Декарт «Рассуждение о методе», часть IV

Современник Декарта Иоганн Кеплер изучал движение планет по орбитам и сформулировал ряд законов, касающихся их траекторий и скорости, однако не нашел простого объяснения тому факту, что планеты движутся именно так, а не иначе.

Исаак Ньютон применил принцип «бритвы Оккама» для описания поведения физических объектов. Его знаменитые законы движения выглядят удивительно просто.

1. Всякий объект в отсутствие приложенной к нему силы продолжает оставаться в состоянии покоя или равномерного прямолинейного движения.

2. Ускорение, которое получает объект, прямо пропорционально приложенной к нему силе.

3. Любые два объекта действуют друг на друга с равными по значению и противоположно направленными силами.

Добавив к этому простое определение силы тяготения, Ньютон сумел вывести открытые Кеплером законы движения планет. Простые объяснения – средство чрезвычайно мощное!

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

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

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

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

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

А вот сумма в 30 долларов выписана от руки. Откуда машине знать, о какой сумме речь, если почерк у каждого свой?

Рис. 2.1. Чек

Задача явно непростая. Взять хотя бы цифру «два» насколько по-разному пишут ее разные люди!

Рис. 2.2. Двойки

Подобными проблемами занимается особая математическая дисциплина – машинное обучение. На первом этапе алгоритм получает большую обучающую выборку (в нашем случае – несколько тысяч примеров написания для каждой цифры). По ней он должен сконструировать относительно несложную модель, которая позволит корректно отличать одну рукописную цифру от другой. Хорошо натренированный алгоритм безошибочно распознает незнакомые цифры даже в том случае, когда обучение завершилось давно.

За последние двадцать лет в этой области удалось добиться впечатляющих успехов. Современные методы классификации данных позволяют анализировать уже не тысячи, а миллионы обучающих примеров. Распознавать теперь можно не только чеки; некоторые программы редактирования изображений умеют вполне сносно фильтровать фотографии по лицам. Сайты интернет-компаний (Amazon, Netflix, Pandora и многие другие) рекомендуют книги, фильмы и музыку, основываясь на ваших предпочтениях и истории покупок. Программы распознавания голоса и автоматического перевода, конечно, не выдерживают конкуренции с человеком, однако дают нам общее представление о смысле написанного или сказанного. Спам-фильтры избавляют нас от нежелательных сообщений, а автомобили к 2020 году научатся ездить практически без нашего участия.

Дальше, очевидно, все станет только лучше. С какого-то момента успехи и достижения польются непрерывным потоком. Значит ли это, что сбривать больше нечего?

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

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

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

Автоматизация творческого процесса

Урбанский алгоритм в сочетании с «бритвой Оккама» позволяет получить практически любые знания – например, понять, что делает картины притягательными, музыку – популярной, а слова – берущими за душу: ведь если P = NP, мы можем просто перебрать все потенциальные варианты. Так мы найдем процедуру распознавания гениальности, а она даст нам возможность быстро находить и гениальные произведения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С небес на землю

Трудно представить, что один-единственный алгоритм способен полностью перевернуть нашу жизнь. Неужели все, что можно описать словами, можно и создать? Неужели можно без труда получать практически любые знания? Звучит невероятно, и именно поэтому большинство ученых не верят в равенство P и NP и полагают, что у нас никогда не будет ни урбанского, ни еще какого-нибудь универсального алгоритма.

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

Глава 3. Классы P и NP

Заклятые друзья

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

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

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

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