Читать «Золотой билет» онлайн - страница 102

Лэнс Фотноу

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.

Яблонский С. В. О невозможности элиминации перебора всех функций из P2 при решении некоторых задач теории схем // Доклады Академии наук СССР, 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.