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

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

Информация о разработке анатомически правильной искусственной руки подчерпнута из выступления Йоки Мацуока на конференции Ассоциации по исследованиям в области вычислительной техники (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.