9.3 Cook定理和Karp问题列表

计算复杂性早期的历史一日千里。1967年，Edmonds刚刚在匹配等组合问题上取得成功，就提出了惊世骇俗的猜想，认为TSP也许根本没有好算法。他的多面体方法对于其他情形都有卓越的效果，他又为何不看好它在旅行商问题上的应用呢？Edmonds含糊其词，不愿解释，只是指出不存在好算法的可能性是合理的。4年之后，Stephen Cook和Richard Karp把这个问题纳入了P与NP问题的大背景中，创立了他们的理论。

9.3.1 复杂性类

数学家喜欢让一切都井井有条。对于复杂性理论而言，这就意味着他们重视判定问题（decision problem），即答案为“是”或“否”的问题。比如，某个图里是不是存在哈密顿回路？要么回答“是”，要么回答“否”。再比如，给定一组城市，是不是存在一条短于1000英里的周游路线？要么回答“是”，要么回答“否”。1

1. 判定问题未必直接体现TSP本质，但是我们总可以提出一系列答案为“是”或“否”的问题，找出最短问题序列对应的最短路线长度。

Richard Karp发明了缩写记号P，用来表示有好算法的判定问题。P类的正式定义是指，能在多项式时间内由一台单带图灵机解决的问题类，换言之，如果输入带上的符号数目为n，那么必定存在指数k和常数C，保证图灵机经过至多为Cnk步以后必然停机。当然，这种定义相当好，单带图灵机可以替换为多带图灵机，甚至换成功能强大的现代数字计算机，也不会影响问题分类。诚然，用图灵机模拟先进计算机会拖慢计算速度，但是速度放慢的系数关于n仍然只是多项式关系。所以，我们如果有先进计算机上的多项式时间算法，就同样拥有单带图灵机上的多项式时间算法。

对判定问题而言，属于P类就意味着完美。不过，Stephen Cook研究了另一类自然出现的问题，其范围或许比P类更大。他概述了Edmonds的看法，考察了能够在多项式时间内验证肯定答案的问题。要想验证答案是否正确，我们同时给出问题叙述和肯定证据，让图灵机检验答案是否确实为肯定的。例如，要想验证一组城市能在1000英里以内周游一遍，提供一条短于1000英里的周游路线作为证据即可。2

2. 这类可在多项式时间内验证问题的概念也曾由Leonid Levin独立提出。

借助非确定性图灵机（nondeterministic Turing machine），可以用另一种方式看待上述证据。非确定性图灵机在计算时能够复制自身，因此它不是真实存在的。如果存在多项式时间的验证算法，那么一台非确定性图灵机就可以创造出自身的多个副本，其中一个副本可以猜中肯定证据，从而确定原问题的答案是肯定的。基于这种看法，Karp提出，可以把Cook研究的问题类简称为NP。

乍一看，似乎NP类远没有P类那么严格，把问题划分为NP类比划分为P类容易得多。TSP就是一例，检验解答容易，找出解答或许很难。再举一个例子，考虑因数分解问题，也就是把给定整数写成两个更小的整数之积。分解过程可能很难（尚未找到多项式时间算法），而要检验某个答案是否正确就是小菜一碟。类似的例子可以构造出很多，不过，它们只能暗示NP类可能比P类范围更大，实际上，对于只属于NP类而不属于P类的问题，我们居然一个也没发现。

9.3.2 问题归约

Stephen Cook的论文开了NP问题正式研究之先河。文中，他提出一道逻辑题可能不属于P类。“另外，上述定理表明，{重言式}（tautology）很可能属于一组不在L内的有趣问题，我认为这一猜想值得花一番工夫尽力解决。若能给出证明，必将取得复杂性理论的重大突破。”1事实上，如今，这个猜想的证明价值百万美金。Cook发表论文时，Karp尚未建立起如今通用的标准术语——Cook所谓的L如今改称为P，而所谓{重言式}如今则通称为可满足性问题（satisfiability problem）。可满足性问题要求确定，对于一系列逻辑变量，能否赋值为真或假，使得给定的表达式取值为真。表达式中用到的量都是这些逻辑变量及其否定（“非”），联结词则为逻辑“且”和逻辑“或”。不过，Cook提出猜想的根据比该问题本身更加重要，因为他的定理表明，每个NP问题都可以表述为可满足性问题。

1. Cook, S. 1971. In: Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing. ACM Press, New York. 151–58.

Cook理论的核心思想是归约，即把问题简而化之。本书中已经多次用到归约思想，例如Karl Menger在维也纳研讨会上曾经提出的问题：寻找经过给定一组点的最短路线。这并不完全等同于TSP，因为并没有要求终点和起点重合。但是，假如我们会求解TSP，那么只需加入一座虚城市，令它与其他给定点之间的旅行成本均为0，就可以依样解决Menger的问题。

问题归约（problem reduction）的正式定义为，在多项式时间内，图灵机接受问题A的任意实例并据此构造出问题B的实例，使得A和B的答案完全相同，要么都为“是”，要么都为“否”。在把Menger问题归约为TSP的时候，我们额外加入了一座城市和n个距离数据，所以，可以设计一台图灵机在正比于n的步骤内实现问题归约，这里n就是原问题给定的点的数目。问题归约大抵如此，你只需牢记一点，问题B的规模不应当过分超出A的规模。

显而易见，在对诸多NP问题进行分类时，归约用途不小。要说明某问题很简单，可以试试把它归约为另一个简单的问题；要说明某问题很难，可以试试把另一道已知的难题归约为它。归约能带来意想不到的有序度：经Cook证明，每个NP问题都可以归约为可满足性问题。

存在大一统问题的理念非常深刻，极其犀利，不过Cook定理的证明其实并没那么难。首先，注意到检验NP问题只需要多项式量级的图灵机步骤，所以把NP问题归约为可满足性问题时，可以在每一步检验步骤里加入标志机器状态和读入符号的逻辑变量。由此便可给出证明，具体细节这里不准备详述，我只想要指出，Cook原始论文里的完整证明也只用了不到一页纸，虽然字号挺小。

现在，我们可以理解Cook的推理过程。从问题A能归约到问题B，蕴涵结论“若B属于P类则A亦属于P类”。因此，如果可满足性问题属于P类，那么所有NP问题都存在多项式时间算法。Cook认为P=NP的可能性不大，由此便提出了上述猜想。

9.3.3 21个NP完全问题

把可满足性问题称为“大一统问题”虽然符合Cook的结论，但是无法全面体现出他的问题归约理论的重要意义。事实上，知道可满足性问题统领NP类，就可以直接证明其他问题同样具有这一性质。

如果某个NP问题可由所有NP问题归约得到，那么它就称为NP完全问题。Cook在证明后写道，可满足性是NP完全的。他的论证很简短，只是指出图论中的子图同构问题同样也是NP完全问题，又证明了可满足性问题可以归约为子图同构问题。因此，NP问题都可以先归约为可满足性问题，再归约为子图同构问题，可以设计一台图灵机，依次执行这两步问题归约，这就证明了子图同构问题是NP完全的。

由于这种连锁式问题归约的思想，复杂性理论领域变得热火朝天，研究领军人物是Richard Karp，他的论文1写于Cook发表结论一年以后。Karp漂亮地给出了P类、NP类、图灵机和问题归约的专业阐述，还提出了如今赫赫有名的21个NP完全问题列表，并列出了Cook可满足性定理给出的归约。列表中，TSP以两种不同面目出现，分别是无向图的哈密顿回路问题和有向图的哈密顿回路问题。

1. Karp (1972).

Karp的论文面世以后，传遍了大街小巷，其他难题的归约也跟风出现，比比皆是，成百上千道问题获证为NP完全问题。1979年，Michael Garey和David Johnson出版了具有里程碑意义的著作，书名为《计算机和难解问题：NP完全导论》（Computers and Intractability: A Guide to the Theory of NP-Completeness），在算法研究圈子里几乎人手一本。每次遇到新问题，研究者总是会先查一遍Garey-Johnson的NP完全问题名录，看看问题归约是否有可用的参照。2

2. Garey和Johnson（1979）极好地介绍了计算复杂性理论。近来，Arora和Barack（2009）也合著了一本优秀的导论。

9.3.4 百万美金

在实践中，一旦证实一个问题为NP完全问题，研究者便会认为它很棘手，不好解决，于是要么使用方便但粗糙的启发式算法，要么使用TSP求解中涌现出的某种辛苦繁重的方法。他们依据的假设是，NP完全问题不可能有高效的多项式时间算法。但是迄今为止，并没有充分靠谱的证据支持P和NP不是一回事。那么，请问本书读者，你支持哪一方观点呢？你认为P=NP，还是P≠NP呢？

如今，计算领域的重要性与日俱增，P与NP问题或许已因此成为整个数学界最知名的未解难题。尽管不断有人做出求解的努力，但是在2009年，Lance Fortnow综述该问题的研究现状时，依然以四个字作结：尚未解决。不过，毕竟有价值百万美金的克雷大奖，我们有理由期待在不久后就将迎来新的进展，正如Wowbagger the Infinitely Prolonged当初的那句台词一样——在道格拉斯•亚当斯的《银河系搭车客指南》（The Hitchiker's Guide to the Galaxy）中，Wowbagger the Infinitely Prolonged打算挑衅宇宙中的每个男人和每个女人，当这项TSP计划的可行性遭到质疑的时候，他回答道：“人总是可以有梦想的，是吧？”