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

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.