Лэнс Фотноу - Золотой билет

Неприступность 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 .

Огромное спасибо моей семье – жене Марси и дочерям Энни и Молли – за любовь и поддержку.

Материалы книги базируются как на моем собственном исследовательском опыте в области сложности вычислений, так и на знаниях, почерпнутых у тысяч других теоретиков и практиков, разделяющих мой интерес к проблеме P и NP. Основой послужили также некоторые статьи из моего блога Computational Complexity.