Читать «Золотой билет» онлайн - страница 100
Лэнс Фотноу
Огромное спасибо моей семье – жене Марси и дочерям Энни и Молли – за любовь и поддержку.
Примечания и список литературы
Материалы книги базируются как на моем собственном исследовательском опыте в области сложности вычислений, так и на знаниях, почерпнутых у тысяч других теоретиков и практиков, разделяющих мой интерес к проблеме P и NP. Основой послужили также некоторые статьи из моего блога
Приведенные в книге истории, примеры и результаты взяты из различных источников, список которых вы найдете ниже.
Все дополнения и изменения, касающиеся источников и ссылок, а также найденные в тексте серьезные ошибки будут выкладываться на сайт книги: http://press. princeton.edu/titles/9937.html. Помимо этого, на сайте приводятся ссылки на использованные статьи, материалы выступлений и некоторую дополнительную информацию, а также список рекомендуемой к прочтению литературы по теме.
Предисловие
Lance Fortnow, «The Status of the P versus NP Problem».
Stephen Hawking,
Глава первая
История Веруки Солт позаимствована из книги
Информация о разработке анатомически правильной искусственной руки подчерпнута из выступления Йоки Мацуока на конференции Ассоциации по исследованиям в области вычислительной техники (CRA) в Сноуберде 18 июля 2010 года.
Примеры задач коммивояжера созданы программой Марка Даскина, см. http://sitemaker.umich.edu/msdaskin/software.
Глава вторая
Почти все в этой главе – вымысел автора, созданный с целью дать читателю представление о фантастическом мире, в котором P = NP. Исключение составляет раздел про «бритву Оккама».
Глава третья
Подробнее об эксперименте Милгрэма можно прочитать в статье
Информация о числе Бэйкона взята с сайта
Проблема четырех красок увлекательно излагается в работе
Глава четвертая
Цитата из Кука – на самом деле не совсем цитата; я перефразировал абзац из основополагающей работы ученого, используя более современные понятия. Приведу здесь оригинальный текст:
«Теорема дает нам основания полагать, что множество тавтологий на самом деле очень интересное, поскольку оно, по всей видимости, не принадлежит L*. Думаю, стоит попытаться доказать данную гипотезу: в теории сложности это стало бы величайшим прорывом».
Steve Cook, «The Complexity of Theorem-Proving Procedures»,
Richard Karp, «Reducibility among Combinatorial Problems»,