4.4　超越卡普的工作

在卡普的论文之后，计算机科学界掀起了一个寻找并证明各种问题是否属于NP完全的热潮。在接下来的几年里，教授和研究生们成功证明了许多已知的搜索问题（以及一些新问题）是NP完全的。一本1979年出版的书¹中列举了三百多个主要的NP完全问题。NP完全问题持续在各个领域涌现，如计算机科学、物理学、生物学、经济学，以及其他许多攀登到困难顶峰的学科。Google学术搜索NP-Complete将返回超过138 000篇科研文献，时间跨度从1972年到2011年，单是2011年就有近1万篇。我们在此无法一一列举，只从中挑选几篇，看看这些文章是什么风格。

^{1 Computers and Intractability: A Guide to the Theory of NP-Completeness, 作者Michael Garey和David Johnson（New York: W. H. Freeman, 1979）。}

1. 支配集（Dominating Set）

敌友国是否存在这样的50个人：其余的人和这50个人中的至少1个是朋友？NP完全问题。

1. 三角切分问题 （Partition into Triangles）

敌友国理工学院的每个宿舍只能容纳三名学生。我们能把所有敌人都安排在不同的宿舍里吗？NP完全问题。