第5章　P和NP诞生前的历史

不要怕蛮力搜索，而是要合理使用它。¹

_{1 Georgy M. Adelson-Velsky Vladimir Arlazarov and Mikhail Donskoy Algorithms for Games (Programirovanie Igr) (New York: Springer-Verlag 1988).}

在上一章中我们讲到了高德纳最终没能为NP完全问题找到一个更恰当的英语单词。如果他当初把眼光投向东方的俄罗斯，就会发现一个合适的词perebor（Перебор），意为“使用蛮力来搜索”，即尝试所有可能性以找到最佳方案。P/NP问题其实是在问，我们是否必须用蛮力搜索来解决团问题，还是存在更快的方法也能达到目的。

但是当年高德纳和其他美国人一样，都很难了解俄罗斯发生的事情。从1945年第二次世界大战结束起，一道铁幕将当时的苏联与东欧，以及美国与西欧隔绝开来。从20世纪50年代开始，冷战导致美国和苏联两国围绕着科技发展展开了一系列竞争，两国都想赢得这场知识领域的“军备竞赛”。由此带来的一个负面影响是基本断绝了东西方科学界的互访和交流。尽管情况在20世纪70年代有所缓和，但直到1991年冷战结束，东西方才恢复了全面的科研交流和讨论。如今，随着大部分的学术成果都被放到网上供人查阅，再加上学者可以较为自由地到世界各地进行学术访问，我们可以认为全球同属一个学术研究社群，而不是被人为地分成两个互不来往的社群。

这一章讲述了两个故事，两条通往P/NP问题的道路。结局是西方的斯蒂芬·库克和东方的列昂尼德·莱文分别率先提出了是否P=NP的问题。但是科学并不是凭空发生的，两边的科研都经过了漫长的路程，最终才可能产生库克和莱文的工作。在本章，我们会截取这两段历史的几个片段进行讲述，包括西方对于高效能计算的本质的苦苦探索，以及东方对蛮力搜索的必要性的理解。最终我们会发现二者殊途同归，走到了P/NP问题面前。