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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 2.1. Чек

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

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

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

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

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

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

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

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

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

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

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

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

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