Cook定理

huangyhg

定理8-7(Cook定理)：布尔表达式的可满足性问题SAT是NP完全的。
PPT下载地址：
http://www.dimcax.com/resource/math/cook.ppt

huangyhg

Cook著名的的NP完全性文章：
The Complexity of Theorem Proving Procedures

Cook在其研究文章中，提出并证明了后来以其名字命名的Cook's Theorem(Cook定理)。关于Cook定理，可参见：
http://en.wikipedia.org/wiki/Cook%27s_theorem

简单而言，Cook证明了SAT(Boolean Satisfiability Problem)问题是一个NP完全性问题。

关于NP完全性问题的定义通常是：

一个可判定性问题C是NP完全的，如果：
1。这个问题是NP问题。
2。所有其他的NP问题可以归约为C问题。

关于NP， P问题，特别是著名的P=NP？的著名难题，可参见：
http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP

关于各种计算复杂性问题的关系图，可参阅：
http://en.wikipedia.org/wiki/Complexity_class   

P是否等价与NP的问题已经成为数学界，计算理论界的一个著名的难题。不管是谁能精确的证明P等价与NP，和P不等价与NP，他/她都可以获得百万美金的悬赏。(编者相信，他/她还会立刻得到图灵奖)。有兴趣的读者可参见：
http://www.claymath.org/millennium/

huangyhg

http://blog.csdn.net/fudan_abc/archive/2008/01/19/2052642.aspx
从容不迫的说：老板，我做不出来，但是，我敢肯定，那些大牛牛们也照样做不出来

boss：原来是这样，那也难为你了。

以上三副图虽然是一个笑话，但也可以为我们的生活研究提供一些思路和指导。当你面对一个问题解决不了时，那么就试图去证明别人也解决不了，这的确是一个偷懒逃避的好借口。我觉得P，NP，NP-c，NP-hard这些名称的出现，就是因为某些难问题，连CS的大牛们都解决不了，无可奈何之下，只好定义一堆东西，为自己找个理由，免得说自己太笨了

言归正传，我们讨论的都是决策问题(说白了就是回答yes/no的问题)，把决策问题按照难易程度分为几类：

(1)P问题。

定义：那些可以在多项式( polynomial )时间内解决的问题，称为P问题。(以后把"多项式时间"，简写为P时间)。时间复杂度如(n^2, n^4,  n(log(n)))都是P时间的，指数级别的如(2^n，n^n)这些就不是P时间了。一个算法的时间复杂度是P时间，哪怕是(n^100)，我们都称这个算法是有效率 effecient 的。

如最大公约数(gcd)，最短路径。但是还有很多问题我们不知道如何在P时间之内解决，如哈密顿路径等等。

(2)NP问题。

定义：给定一个解，我们可以在P时间内检查他正确与否的决策问题，成为NP( Non-deterministic polynomial )问题。

比如，我要找一个图的哈密顿路径，随便给我一个解，我都可以在P时间内检查它是不是哈密顿路径。只要形如定义的问题，就是NP问题。所以，P问题是属于NP问题的，因为给定一个P问题，我可以在P时间内找到答案，那么任意给我一个解，我简单的比较解和答案是不是相同，就可以回答yes/no，整个时间是P，符合定义。

(3)NP-c问题。

有意思的东西来了，在NP问题这一个大类里面，包含了太多太多的问题，有的很简单，如P问题，有的很困难，如找哈密顿路径。我们必须把这些同志区别开来。所以就定义了NP-c问题。

定义：NP-c问题是这样的一类问题，首先他是属于NP的，而且他是NP问题里面最难解决的问题。难到什么程度？只要其中某个问题可以在P时间内解决，那么所有的NP问题就都可以在P时间内解决了。

NP-c问题的定义出来了，但是，它忽悠了半天，除了说明这类问题比较难之外，其他啥也没有。我们还是不知道到底什么问题是NP-c问题，如何判定一个问题是不是NP-c问题。

1970年，太阳出来了，十月革命一声炮响，cook同志发明了cook定理，找到了第一个NP-c问题，SAT(Satisfiability)问题。他是这么说的，如果SAT问题可以在P时间解决，那么所有的NP问题都可以在P时间内解决。

我靠，现在好了，我们知道了一个NP-c问题，下面的问题就好办了，要判断一个问题 Q 是不是相当难问题，是不是一个NP-c问题。那么我们要做的事情就是，第一步，判断Q是不是NP（这好办），第二步，判断Q这个问题的难度是不是比cook同志提出来的SAT问题还要难，如果Q比SAT问题还难，我靠，没希望了，丫肯定是NP-c。。。

判断两个问题Q，R的难易程度，我们可以这么来做。具体的套路叫做多项式归约(polynomial time reduction)，意思是，我们要解决R，但是我们可以先把问题在多项式时间内转化成Q问题，只要解决了Q问题，R问题就解决了。如果问题R可以多项式归约到Q，那么Q一定不比R容易。记为R<=Q。

好了，我们就可以从第一个NP-c问题出发，一层一层的把问题转化下去，形成了NP-c问题的树。(这些问题的相互转化，很有意思，相当精彩！)