NP猜想（一） (4-4)

由于任何NP类问题都可以归约到一个NPC问题，那么如果求解这个NPC问题存在多项式时间复杂度的算法，也就是说如果这个NPC问题是“P类问题”，就意味着任何NP类问题都是“P类问题”，即“NP=P”成立了。这就是NPC问题在解决“NP=P”问题中的巨大价值。

另外，根据归约关系的可传递性，如果某一个问题L₁ 是NPC问题，并且这个问题还可以归约到另外一个NP类问题 L₂ ，也即 L₁ ∝ L₂ ，那么 L₂ 也必然是一个NPC问题。换句话说，如果存在多个NPC问题，那么这些NPC问题之间是可以互相归约的，也就是说任意两个NPC问题的难度都是一样的。

（二）第一个被发现的NPC问题及其证明思路

找到一个NPC问题是很不容易的，特别是找到第一个NPC问题更不容易。一度人们曾经怀疑是否真的存在NPC问题。

前面提到，1971年库克教授在论文中提出了第一个NPC问题并给出了证明。这使得世人知道了这类NPC问题是真的存在的。库克教授给出的这第一个NPC问题叫做“SAT问题”，又称作“可满足性问题”，英文为“The Satisfiability Problem”，SAT是Satisfiability单词的前三个字母。“SAT问题是一个NPC问题”这个结论被称作库克定理。其实SAT问题就是我们前面在介绍时间复杂度的时候提到的例子（3），只不过换了个说法而已，库克教授论文中用的就是例子（3）中的说法，判断是否是重言表达式。

如今的SAT问题被定义为“给出一个含有n个逻辑变量的逻辑表达式，判断这个表达式是否可能取值为真，也就是判断这个逻辑表达式是否是可被满足的”，所以它又叫做“可满足性问题”。

解决SAT问题并不像看起来这么简单，目前已知的各类解决SAT问题的算法的时间复杂度都是较高的，都大于多项式时间。同样的，证明SAT问题是NPC问题也不是一个简单的事，因为我们需要证明任何NP类问题都可以在多项式时间复杂度内归约为SAT问题。

库克教授找到了一个非常巧妙的方法给出了这个证明。这个方法是基于伟大的英国数学家、罗辑学家、计算机科学之父艾伦·麦席森·图灵（Alan Mathison Turing，1912年6月23日－1954年6月7日）设计的“图灵机”。提到图灵，为了以示尊敬，我得先漱漱口、洗洗手再来码字写这篇文章，因为他实在是太伟大了。

... ... ... ...

好，洗漱完毕后，我们来介绍库克教授的证明思路。之所以仅仅介绍证明思路，是因为全部证明过程涉及到比较复杂的逻辑表达式构造，算不上很优美。但是，其证明思路与框架确实非常巧妙，充分体现了逻辑学的优美。

由于库克定理的证明主要基于非确定图灵机，我们先要简单介绍一下图灵机与非确定图灵机。

1、神奇而伟大的图灵机

图灵机，又称图灵计算、图灵计算机，是由伟大的图灵提出的一种抽象计算模型。它将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。

控制器

α₁

↓

读写头 图灵机

α₁α₂……αᵢ……αₙ……带子

图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：

一是在纸上写上或擦除某个符号；二是把注意力从纸的一个位置移动到另一个位置。而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和（b) 此人当前思维的状态。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。