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

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

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

Технология, проработавшая без сбоев долгое время, становится потенциально опасной. Мы начинаем слишком доверять ей, и нам кажется, будто все и дальше будет так же хорошо. Неприятности обычно застают нас врасплох; чем реже они случаются, тем меньше мы оказываемся готовы к ним. Ярчайшие примеры – разрушенные ураганом «Катрина» дамбы в Нью-Орлеане, обширный разлив нефти в Мексиканском заливе после взрыва буровой платформы в 2010 году, а также авария на японской АЭС «Фукусима-1» в 2011 году, спровоцированная землетрясением и последовавшим за ним цунами. С технологией следует обращаться как с диким животным. Следующая крупная авария не должна привести к глобальной катастрофе (впрочем, будем надеяться, что она не случится).

Доказать неравенство P и NP будет очень и очень непросто. Ведь для этого придется обосновать тот факт, что с задачей о клике (или с любой другой NP-полной задачей) не справится ни один известный – а также неизвестный – эффективный алгоритм. Но как можно рассуждать о неизвестных алгоритмах?

Впрочем, я почти уверен, что неравенство классов докажут. Произойдет это нескоро – лет через двадцать, а может, через два столетия или даже два тысячелетия, однако в конце концов мы все же разработаем методы, которые позволят доказать, что P и NP не равны. Математики придут в настоящий экстаз и наперебой заговорят о «великом решении великой проблемы». Новые техники подведут нас к самой сути эффективных вычислений, а они со временем проникнут во все сферы нашей жизни.

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

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

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

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

Прежде всего я хотел бы поблагодарить Моше Варди, который вдохновил меня на написание обзорной статьи для журнала Communications of the ACM и сам ее отредактировал. Статья вышла под названием The Status of the P versus NP Problem; ее популярность навела меня на мысль развить тему и выпустить книгу, доступную для широкой аудитории.

Пока я занимался книгой, Уильям Гасарч, с которым мы вместе ведем блог, всячески меня поддерживал и читал каждую главу еще в самом черновом и притом рукописном варианте. Помимо Уильяма предварительную версию всей книги изучили Алана Лидовер, а также Джон, Джим и Крис Пуртило, которые высказали много ценных замечаний. Черновики отдельных глав проверяли Куан-Линг Чен, Джош Грочоу, Ральф Хансен, Адам Калинич, Дэвид Пеннок и Рахул Сантанам; их советы также очень помогли мне.

Мануэль Блюм, Стивен Кук, Дэвид Джонсон, Леонид Левин, Альберт Мейер поделились со мной своими мнением относительно зарождения проблемы равенства P и NP. Благодаря Александру Разборову я немного разобрался с советской историей.

Вся моя научная деятельность в области теоретической информатики, все мое рабочее окружение – исследователи, студенты и многие другие (привести здесь полный список не представляется возможным) – в той или иной мере повлияли на написание этой книги. Особую признательность хочу выразить моим коллегам из Калифорнийского университета в Беркли, Массачусетского технологического института, Чикагского университета, Центра математики и информатики в Амстердаме, научно-исследовательского института NEC, Технологического института Toyota в Чикаго и Северо-Западного университета: я очень ценю нашу дружбу и наши интересные беседы.

Мои первые представления о проблеме равенства P и NP сформировались под влиянием двух людей, которые, безусловно, заслуживают отдельного упоминания: это Юрис Хартманис, который познакомил меня с P и NP, когда я еще был студентом Корнелльского университета, и Майкл Сипсер, под руководством которого я писал диссертацию в Калифорнийском университете и в Массачусетском технологическом институте.

За примерами раскраски карт в шестой главе мне пришлось обратиться в интернет; хочу поблагодарить всех, кто откликнулся: это Крис Богарт, Хсиен-Чих Чанг, Палволги Домотор, Дэвид Эпштейн, Лукас Грабовски, Гил Калай, Чарльз Мартель и Деррик Столи.

Книгу я писал, будучи профессором электротехники и информатики в Школе инженерии и прикладных наук имени Роберта Маккормика при Северо-Западном университете. Университет очень поощряет книжные проекты, направленные на популяризацию научных знаний. Я активно пользовался всеми доступными ресурсами, в особенности обширной библиотекой, представленной как на цифровых носителях, так и в бумажном виде. В университете работают замечательные люди; мой помощник по административной части Марджори Рейес оказала мне неоценимую помощь.

Мой принстонский редактор Вики Керн дала мне множество толковых советов и тщательно вычитывала рукопись на всех стадиях ее создания; благодаря ей книга стала намного лучше. Также я очень признателен ее помощнику Куинну Фустингу и вообще всем сотрудникам издательства Princeton University Press.