【CT】【转】第一个 NP-complete 问题

NP 是 Non-deterministic Polynomial 的缩写，NP 问题通俗来说是其解的正确性能够被很容易检查的问题，这里"很容易检查"指的是存在一个多项式检查算法。

例如，著名的推销员旅行问题（Travel Saleman Problem or

TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。

任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销 $C 块钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于

$C？

推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 $C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排! 这将是个天文数字。

NP-complete 问题是所有 NP 问题中最难的问题。它的定义是，如果你可以找到一个解决某个 NP-complete 问题的多项式算法，那么所有的 NP 问题都将可以很容易地解决。

通常证明一个问题 A 是 NP-complete 需要两步，第一先证明 A 是 NP 的，即满足容易被检查这个性质; 第二步是构造一个从某个已知的

NP-complete 问题 B 到 A 的多项式变换，使得如果 B 能够被容易地求解，A 也能被容易地解决。这样一来，我们至少需要知道一个

NP-complete 问题。

第一个 NP complete 问题是 SAT 问题，由 COOK 在 1971 年证明。SAT 问题指的是，给定一个包含 n 个布尔变量（只能为真或假） X1，X2，…，Xn

的逻辑析取范式，是否存在它们的一个取值组合，使得该析取范式被满足? 可以用一个具体例子来说明这一问题，假设你要安排一个 1000 人的晚宴，每桌

10 人，共 100 桌。主人给了你一张纸，上面写明其中哪些

人因为江湖恩怨不能坐在同一张桌子上，问是否存在一个满足所有这些约束条件的晚宴安排? 这个问题显然是 NP

的，因为如果有人建议一个安排方式，你可以很容易检查它是否满足所有约束。COOK 证明了这个问题是 NP-complete

的，即如果你有一个好的方法能解决晚宴安排问题，那你就能解决所有的 NP 问题。

这听起来很困难，因为你必须面对所有的 NP 问题，而且现在你并不知道任何的 NP-complete 问题可以利用。COOK 用非确定性图灵机（ Non-deterministic Turing Machine ） 巧妙地解决了这一问题。