Лэнс Фотноу - Золотой билет
Карта провинций королевства создана по аналогии с некоторыми примерами в статье 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/
Примечания
1
Перевод: М. Барон, Е. Барон.
2
Мое число Эрдёша равно двум, поскольку у меня имеются совместные публикации с тремя его соавторами. В единицу оно уже вряд ли когда-нибудь превратится: Пал Эрдёш умер в 1996 году. Актерский опыт у меня отсутствует (талант, впрочем, тоже), так что мое число Бэйкона не определено.
3
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982 / Michael Garey, David Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. – W. H. Freeman, New York, 1979.
4
B. A. Trakhtenbrot. A Survey of Russian Approaches to Perebor Algorithms // Annals of the History of Computing vol. 6, no. 4 (October 1984).
5
Разве мы с вами только что не доказали истинность этого высказывания? На самом деле нет: ведь мы действовали в предположении, что все, что можно доказать, истинно. Однако Гёдель показал, что утверждение «Все, что можно доказать, истинно» также нельзя доказать, если только мы не умеем доказывать ложные утверждения. Вот что можно узнать, читая сноски!
6
На русском языке: Роальд Даль «Чарли и шоколадная фабрика». – Прим. перев.
