Примечания книги Золотой билет. P, NP и границы возможного. Автор книги Лэнс Фортноу

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

На русском языке: Роальд Даль «Чарли и шоколадная фабрика». – Прим. перев.