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

Прежде всего я хотел бы поблагодарить Моше Варди, который вдохновил меня на написание обзорной статьи для журнала 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.

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

Все дополнения и изменения, касающиеся источников и ссылок, а также найденные в тексте серьезные ошибки будут выкладываться на сайт книги: http://press. princeton.edu/titles/9937.html. Помимо этого, на сайте приводятся ссылки на использованные статьи, материалы выступлений и некоторую дополнительную информацию, а также список рекомендуемой к прочтению литературы по теме.

Предисловие

Lance Fortnow, «The Status of the P versus NP Problem». Communications of the ACM 52, no. 9 (September 2009): 78–86.

Stephen Hawking, A Brief History of Time: From the Big Bang to Black Holes (New York: Bantam Dell, 1988).

Глава первая

История Веруки Солт позаимствована из книги Roald Dahl, Charlie and the Chocolate Factory (New York: Knopf, 1964).

Информация о разработке анатомически правильной искусственной руки подчерпнута из выступления Йоки Мацуока на конференции Ассоциации по исследованиям в области вычислительной техники (CRA) в Сноуберде 18 июля 2010 года.

Примеры задач коммивояжера созданы программой Марка Даскина, см. http://sitemaker.umich.edu/msdaskin/software.

Глава вторая

Почти все в этой главе – вымысел автора, созданный с целью дать читателю представление о фантастическом мире, в котором P = NP. Исключение составляет раздел про «бритву Оккама».

Глава третья

Подробнее об эксперименте Милгрэма можно прочитать в статье Stanley Milgram, «The Small World Problem», Psycology Today 2, no. 1 (1967): 60–67.

Информация о числе Бэйкона взята с сайта Internet Movie Database.

Проблема четырех красок увлекательно излагается в работе Robin Wilson, Four Colors Suffice: How the Map Problem Was Solved (Princeton, NJ: Princeton University Press, 2004).

Глава четвертая

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

«Теорема дает нам основания полагать, что множество тавтологий на самом деле очень интересное, поскольку оно, по всей видимости, не принадлежит L*. Думаю, стоит попытаться доказать данную гипотезу: в теории сложности это стало бы величайшим прорывом».

Steve Cook, «The Complexity of Theorem-Proving Procedures», Proceedings of the Third Annual ACM Symposium on Theory of Computing (New York: ACM), 151–58.

Richard Karp, «Reducibility among Combinatorial Problems», Complexity of Computer Computations 40, no. 4 (1972): 85–103.

Bob Sehlinger (author) and Len Testa (contributor), The Unofficial Guide Walt Disney World 2010 (New York: Wiley, 2010).

Раздел «Что в имени?» основывается на работе Donald Knuth, «A Terminological Proposal», ACM SIGACT News 6, no. 1 (January 1974): 12–18.

Kevin Sack, «60 Lives, 30 Kidneys, All Linked», New York Times, February 19, 2012, A1.

Глава пятая

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

Lance Fortnow and Steve Homer, «A Short History of Computational Complexity», Bulletin of the European Association for Theoretical Computer Science 80 (June 2003); «Computational Complexity» column.

Dennis Shasha and Cathy Lazere, «A Good Solution Is Hard to Find», Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (New York: Springer, 1995).

Juris Hartmanis, «Observations about the Development of Theoretical Computer Science», Annals of the History of Computing 3, no. 1 (January 1981): 42–51.

B. A. Trakhtenbrot, «A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms», Annals of the History of Computing 6, no. 4 (October 1984): 384–400.

Michael Sipser, «The History and Status of the P versus NP Question», Proceedings of the 24th Annual ACM Symposium on Theory of Computing (New York: ACM, 1992), 603–18. (В этой статье приводится оригинал письма Гёделя фон Нейману и его английский перевод.)

Дополнительным источником послужили личные беседы с некоторыми учеными, включая Стивена Кука и Леонида Левина.

Колмогоров действительно пробовал свои силы в истории; данный факт подтвердили российские участники международного семинара «Колмогоровская сложность и ее приложения», проведенного в честь столетия со дня рождения ученого (Дагштул, Германия, 27 апреля – 2 мая 2003 года). 1 мая 2003 года я написал об этом в своем блоге Computational Complexity.

Историю о том, как Колмогоров спас теорию вероятностей, однажды упомянул Александр Разборов; она также приводится в блоге http://ansobol.livejournal.com/12551.html?thread=235015. Из текста можно заключить, что это все-таки, наверное, анекдот.

Литература

Alan Cobham, «The Intrinsic Computational Difficulty of Functions», in Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science, 24–30.

Stephen Cook, «The Complexity of Theorem-Proving Procedures», in Proceedings of the Third Annual ACM Symposium on Theory of Computing (New York: ACM, 1971), 151–58.

Jack Edmonds, «Paths, Trees and Flowers», Canadian Journal of Mathematics 17 (1965): 449–67.

Juris Hartmanis and Richard Stearns, «On the Computational Complexity of Algorithms», Transactions of the American Mathematical Society 117 (1965): 385–406.

Richard Karp, «Reducibility among Combinatorial Problems», Complexity of Computer Computations 40, no. 4 (1972): 85–103.

Левин Л. А. Универсальные задачи перебора // Проблемы передачи информации, т. 9 (1973), вып. 3, с. 115–116.

Warren McCulloch and Walter Pitts, «A Logical Calculus of the Ideas Immanent in Nervous Activity», Bulletin of Mathematical Biology 5, no. 4 (1943): 115–33.

Panel discussion, Complexity of Computer Computations 40, no. 4 (1972): 169–85.

Alan Turing, «On Computable Numbers, with an Application to the Entscheidungsproblem», Proceedings of the London Mathematical Society 42 (1936): 230–65.

Яблонский С. В. О невозможности элиминации перебора всех функций из P₂ при решении некоторых задач теории схем // Доклады Академии наук СССР, 1959, т. 124, № 1, с. 44–47.

Журавлев Ю. И. О невозможности построения минимальных дизъюнктивных нормальных форм функций алгебры логики в одном классе алгоритмов // Доклады Академии наук СССР, 1960, т. 132, № 3, с. 504–506.

Глава шестая

Пример задачи коммивояжера взят из пресс-релиза Центра исследований параллельных вычислений при университете Райса (CRPC Researchers Solve Traveling Salesman Problem for Record-Breaking 13,509 Cities, 2003).

Когда мне потребовалась помощь с эвристическими алгоритмами и примерами раскраски карт, я обратился за консультацией в раздел вопросов и ответов на сайте http://cstheory.stackexchange.com/questions/4027/coloring-planar-graphs, а также опубликовал вопрос в своем блоге.

Карта провинций королевства создана по аналогии с некоторыми примерами в статье David P. Dailey, Uniqueness of Colorability and Colorability of Planar 4-Regular Graphs Are NP-Complete, Discrete Mathematics 30 (1980): 289–93.

Глава седьмая

Процитированную в начале главы фразу Юрис Хартманис произнес весной 1985 года, когда читал курс в Корнелльском университете.

С редакционной политикой журнала Journal of the ACM относительно проблемы равенства P и NP можно ознакомиться по ссылке: http://jacm.acm.org/instructions/pnp.

Работу Деолаликара я получил от него самого: я был среди тех двадцати двух специалистов, которым 6 августа 2010 года Винэй Деолаликар направил по электронной почте письмо с приложенным к нему доказательством.

О деятельности Джероламо Кардано подробно рассказано в книге David Kahn, The Codebreakers: The Story of Secret Writing (New York: Macmillan, 1967).

Глава восьмая

Сведения об истории развития криптографии по большей части почерпнуты из книги David Kahn, The Codebreakers: The Story of Secret Writing (New York: Macmillan, 1967).

Примеры судоку с нулевым разглашением перекочевали в книгу из моего блога Computational Complexity (запись от 3 августа 2006 года): http://blog.computationalcomplexity.org/2006/08/zero-knowledge-sudoku.html.

Литература

Whitfield Diffie and Martin Hellman, «New Directions in Cryptography», IEEE Transactions on Information Theory 22, no. 6 (November 1976): 644–54.

Craig Gentry, «Fully Homomorphic Encryption Using Ideal Lattices», in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (New York: ACM, 1979), 169–78.

Ronald Rivest, Adi Shamir, and Leonard Adleman, «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems», Communications of the ACM 21, no. 2 (February 1978): 120–26.

Глава девятая

Представление о той роли, которую Ричард Фейнман сыграл в развитии квантовых вычислений, я получил из работы David Deutsch, «Quantum Computation», Physics World, January 6, 1992.

Литература

Charles Bennett and Gilles Brassard, «Quantum Cryptography: Public Key Distribution and Coin Tossing», Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing (Amsterdam: Elsevier, 1984), 175–79.

Charles Bennett, Gilles Brassard, Claude Crepeau, Richard Jozsa, Asher Peres, and William K. Wootters, «Teleporting an Unknown Quantum State via Dual Classical and Einstein-Podolsky-Rosen Channels», Physical Review Letters 70 (1993): 1895–99.

Lov Grover, «A Fast Quantum Mechanical Algorithm for Database Search», in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (New York: ACM, 1996), 212–19.

Stephen Pincock, Codebreaker: The History of Codes and Ciphers (New York: Walker and Co., 2006), 151.

Peter Shor, «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer», SIAM Journal on Computing 26 (1997): 1484–1509.

Глава десятая

Закон Мура опубликован в работе Gordon Moore, «Cramming More Components onto Integrated Circuits», Electronics 38, no. 8 (April 19, 1965).

Об устройстве Уотсона рассказано в блоге IBM: «What Runs IBM Watson and Why», David Davidian.

Историю создания контейнеровозов см. в книге Marc Levinson, The Box: How the Shipping Container Made the World Smaller and the World Economy Bigger (Princeton, NJ: Princeton University Press, 2008)

Ссылки на статистику по большим данным

http://www.youtube.com/t/press_statistics

http://techcrunch.com/2011/03/14/new-twitter-stats-140m-tweets-sent-per-day-60k-accounts-created-per-day/

http://www.facebook.com/press/info.php?statistics

http://email.about.com/od/emailtrivia/f/emails_per_day.htm

http://public.web.cern.ch/public/en/lhc/Computing-en.html

http://space.about.com/od/telescopesandoptics/p/hubbleinfo.htm

http://webbtelescope.org/webb_telescope/technology_at_the_extremes/quick_facts.php

http://royal.pingdom.com/2011/01/12/internet-2010-in-numbers/