章节注释和文献

本书的内容基于我对计算复杂度领域的研究经验，以及与几千个来自学术界和工业界同样对P/NP问题感兴趣的研究者。书中的一些内容改编自我的博客“Computational Complexity”（计算复杂度）。

在著书过程中，我从许多资料引用了一些故事、例子和结果。下面将列出所有的资料。

所有对于这些资料或链接的更新，以及文中发现的重大错误，都将公布在本书的网站http://press.princeton.edu/titles/9937.html上。网站也提供了引用的图书、访谈、附加信息以及P/NP问题的拓展阅读等内容。

前言

Lance Fortnow, “The Status of the P versus NP Problem,” Communications of the ACM 52, no. 9 (September 2009): 78–86.

Stephen Hawking, A Brief History of Time: From the Big Bang to Black Holes (New York: Bantam Dell, 1988).

第1章

维露卡·索尔特的故事是从罗尔德·达尔的小说Charlie and the Chocolate Factory (New York: Knopf, 1964)中摘录的。

对松冈容子工作的讨论，即她的科研小组研发的解剖学上正确无误的机械手，信息来自2010 CRA Snowbird Conference（2010年7月18日）上的一场讲座。

旅行推销员问题是用Mark Daskin的软件生成的，网址是http://sitemaker.umich.edu/msdaskin/software。

第2章

除了2.4节，本章其余内容都是我虚构的，目的是为了描绘不太可能发生的P=NP的世界。

第3章

关于米尔格拉姆的实验，参见Stanley Milgram, “The Small World Problem,” Psychology Today 2, no. 1 (1967): 60–67。

贝肯分数的计算来自Internet Movie Database。

对于四色问题有一本可读性更强的故事，参见Robin Wilson, Four Colors Suffice: How the Map Problem Was Solved (Princeton, NJ: Princeton University Press, 2004)。

第4章

引用库克的话其实有修改，经过了一些现代术语的替换。原文如下：

The theorems suggest that {tautologies} is a good candidate for an interesting set not in L*, and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.

Steve Cook, “The Complexity of Theorem-Proving Procedures,” in Proceedings of the Third Annual ACM Symposium on Theory of Computing (New York: ACM), 151–158.

卡普的后续论文指的是：Richard Karp, “Reducibility among Combinatorial Problems,” Complexity of Computer Computations 40, no. 4 (1972): 85–103。

Bob Sehlinger (author) and Len Testa (contributor), The Unofficial Guide Walt Disney World 2010 (New York: Wiley, 2010).

4.3节内容取材自Donald Knuth, “A Terminological Proposal,” ACM SIGACT News 6, no. 1 (January 1974): 12–18。

Kevin Sack, “60 Lives, 30 Kidneys, All Linked,” New York Times, February 19, 2012, A1.

第5章

本章从以下资料汲取了很多素材。

Lance Fortnow and Steve Homer, “A Short History of Computational Complexity,” Bulletin of the European Association for Theoretical Computer Science 80 (June 2003)，“Computational Complexity” 专栏，以及与许多研究者的个人讨论（包括斯蒂芬·库克和列昂尼德·莱文）。

Dennis Shasha and Cathy Lazere, “A Good Solution Is Hard to Find,” in Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (New York: Springer, 1995).

Juris Hartmanis, “Observations about the Development of Theoretical Computer Science,” Annals of the History of Computing 3, no. 1 (January 1981): 42–51.

B. A. Trakhtenbrot, “A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms,” Annals of the History of Computing 6, no. 4 (October 1984): 384–400.

Michael Sipser, “The History and Status of the P versus NP Question,” in Proceedings of the 24th Annual ACM Symposium on Theory of Computing (New York: ACM, 1992), 603–618. 这篇文章中包含了哥德尔写给冯·诺依曼的信件副本和英文译文。

柯尔莫哥洛夫曾经试图成为历史学家的故事得到了几个俄罗斯人的印证，时间是在2003年4月27日至5月2日，地点是在德国的Dagstuhl召开的柯尔莫哥洛夫复杂度及应用百年座谈会上。这个故事也记录在我的博客“Computational Complexity”上，时间是2003年5月1日。

参考文献

Alan Cobham, “The Intrinsic Computational Difficulty of Functions,” in Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science, 24–30.

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–158.

Jack Edmonds, “Paths, Trees and Flowers,” Canadian Journal of Mathematics 17 (1965): 449–467.

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.

Leonid Levin, “Universal Sequential Search Problems” [in Russian], Problemy Pred. Informatsii 9, no. 3 (1971): 265–266. Translation in B. A. Trakhtenbrot, “A Survey of Russian Approaches to Prebor (Brute-Force Search) Algorithms,” Annals of the History of Computing 6, no. 4 (October 1984): 384–400.

Warren McCulloch and Walter Pitts, “A Logical Calculus of the Ideas Immanent in Nervous Activity,” Bulletin of Mathematical Biology 5, no. 4 (1943): 115–133.

Panel discussion, Complexity of Computer Computations 40, no. 4 (1972): 169–185.

Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society 42 (1936): 230–265.

S. Yablonsky, “On the Impossibility of Eliminating PEREBOR in Solving Some Problems of Circuit Theory,” Doklady Akademii Nauk SSSR 124 (1959): 44–47.

Y. Zhuravlev, “On the Impossibility of Constructing Minimal Disjunctive Normal Forms for Boolean Functions by Algorithms of a Certain Class,” Doklady Akademii Nauk SSSR 132 (1960): 504–506.

第6章

旅行推销员问题¹的例子来自“CRPC Researchers Solve Traveling Salesman Problem for Record-Breaking 13,509 Cities”，2003年由莱斯大学并行计算研究中心举行的一次新闻发布会。

^{1 旅行推销员问题是用Mark Daskin 的软件生成的，网址是http://sitemaker.umich. edu/msdaskin/software。}

为了找到地图填色的启发式方法的例子，我向网络社区寻求了帮助，在答疑网站（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–293。

第7章

第一句中引用尤里斯·哈特马尼斯的话来自于他1985年春季在康奈尔大学讲的一堂课上。

关于P/NP策略，参见JACM的相关页面（http://jacm.acm.org/instructions/pnp）。

维纳里·德奥拉利卡的P/NP论文附加在他于2010年8月6日发送的一封电子邮件中，收信人是我和其他21个研究者。

吉罗拉莫的故事参见David Kahn, The Codebreakers: The Story of Secret Writing (New York: Macmillan, 1967)。

第8章

本章关于密码学早期历史的叙述很多都来自David Kahn的著述，The Codebreakers: The Story of Secret Writing (New York: Macmillan, 1967)。

零知识证明数独的例子源于我在2006年8月3日撰写的一篇博文，发布在我的博客“Computational Complexity”上：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–654.

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–178.

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–126.

第9章

我对理查德·费曼在量子计算学中起到的作用的叙述取材自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–179.

Charles Bennett, Gilles Brassard, Claude Crépeau, 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–1899.

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–219.

Stephen Pincock, Codebreaker: The History of Codes and Ciphers (New York: Walker and Co., 2006), 151, for the Bennett and Brassard beach story.

Peter Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Loga-rithms on a Quantum Computer,” SIAM Journal on Computing 26 (1997): 1484–1509.

第10章

摩尔定律来自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-460k-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/