Золотой билет

Благодарности

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

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

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

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

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

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

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

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

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