NP猜想（一）

P＝NP？

P、NP、NPC、NP、hard

1900年，德国大数学家大卫·希尔伯特在巴黎提出了23个待解决的数学问题，这些问题直接影响、指导了一百多年的数学研究方向。为了呼应一个世纪前希尔伯特在世纪之初通过提问题而指导研究方向的传统，2000年5月24日美国克雷数学研究所( Clay Mathematics Institute , CMI ) 公布了七个有待证明或证伪的数学猜想，并为每个猜想给出了100万美金的奖金。

科学发展越来越深入，学科专业划分越来越细致，可能如今已经没有像当年的希尔伯特那样的集大成的数学家了，所以这七个问题是由证明了费马大定理的英国数学家安德鲁·怀尔斯、菲尔兹奖和阿贝尔奖双奖获得者英国数学家阿蒂亚（前些日子声称证明了黎曼猜想的那个老人）、美国数学家阿贝尔奖获得者约翰·泰特、法国数学家阿兰·孔涅（ Alain Connes ）、弦论创始人美国数学家物理学家威滕等科学家共同讨论确定的。

这七个问题可以说在当今数学及数学物理领域是赫赫有名，其中的第一个问题就是被称为“NP=P”的问题。这是一个看起来不太像传统数学猜想的问题，其实它属于计算复杂性理论的问题，IT行业的人士可能对这个问题更熟悉一些。今天我们就来聊聊这个问题。

一、“NP=P”到底是个什么问题？

要知道“NP=P”是个什么问题，先要知道什么是“P类问题”，什么是“NP类问题”，而这两个概念又和计算理论中的时间复杂度有关。不过不用担心，这几个概念都不是很复杂。

简单的说，解决一个问题的某种算法所需要的计算量（或计算步骤）随着这个问题的规模增长而增长的速度就被称为这个算法的时间复杂度。要注意的是，时间复杂度本质上指的是计算量增长的速度而不是这个算法运行的时间。例如：

（1）我们要计算前n个自然数的和，如果使用最直接而笨拙的方法，需要计算n-1次加法，那么可以认为这个算法的时间复杂度就是“n-1”，记作O(n-1)或者O(n)。之所以可以记作O(n)，是因为随着n的增大，1这个常数就忽略不计了。

（2）如果我们要把n个不同的自然数排序，那么就需要对这些自然数的大小进行比较。我们也采用最笨拙的算法，也就是将每两个自然数都做一次比较，那么需要比较n(n-1)/2次，时间复杂度可以记为

n² n

O(─ – ─)

2 2

n²

，或者记为O(─) 。

2

（3）下面举一个更复杂些的例子。给出一个含有n个逻辑变量的逻辑表达式，请判断这个表达式是否是一个“重言”的逻辑表达式。“重言”的意思是说这个表达式无论所包含的n个逻辑变量怎么取值，其结果都是真，类似于我们语言中的“废话”（如“明天要么下雨要么不下雨”）。最简单的重言表达式如 A∨ˉA ，其结果永远为真。我们如果也采用最笨拙的算法，穷举出n个逻辑变量的全部可能的组合，计算每种组合下逻辑表达式的值，如果都是真，就说明这个逻辑表达式是重言的。n个逻辑变量全部可能的组合有 2ⁿ 种，每种组合要进行大约P(n)次逻辑运算（P(n)是n的某个多项式），因此其时间复杂度为O(P(n) · 2ⁿ)

当然，对于同样的问题，采用不同的算法其时间复杂度不一定相同。如果某个问题，我们能够找到的最优算法的时间复杂度是n的多项式函数，我们就说这个问题属于“P类问题”。这里面的P就是多项式的英文（Polynomial）的首字母。前面例子中的（1）和（2）就属于“P类问题”。

还有一些问题，无论其是否能够在多项式时间复杂度内求解，至少我们知道如果随便给出一个可能的解，我们可以在多项式时间复杂度内验证其是否为所求的解。这类问题我们称之为“NP类问题”。比如前面的例子（3），我们随便猜测一组逻辑变量的组合，就可以通过P(n)次逻辑运算判定其结果是否为假，如果是，那么我们就确定这个逻辑表达式不是重言表达式。因此，（3）中的问题虽然我们还没有找到一个多项式时间复杂度的算法，不知道它是否属于“P类问题”，但是我们很确定它一定属于“NP类问题”。

之所以要研究一个问题是否有多项式时间复杂度的算法，是因为多项式时间复杂度的计算量增长速度相对来说算是“慢”的，随着n的增大，其计算量远远小于O(2ⁿ) 、 O(n！) 、 O(nⁿ) 等时间复杂度问题。比如很有名的大整数质因数分解问题，给出一个2048位的二进制整数，要找到它的某个质因数，一般情况下穷尽全世界的计算能力也不能在100年内完成这个求解计算过程；但是如果我给出一个质数，却可以用普通的计算机在几秒钟时间以内确定这个质数是否是这个2048位二进制整数的一个因数。这就是不同时间复杂度在实际计算过程中的差别！

知道了什么是“P类问题”，什么是“NP类问题”，我们就很容易知道，全部的“P类问题”都属于“NP类问题”，也就是“NP类问题集合”⊇ “P类问题集合”。这是显然的，一个问题可以在多项式时间复杂度内求解，当然可以在多项式时间复杂度内验证。但是反过来，一个可以在多项式时间复杂度内验证的问题是否一定能够通过多项式时间复杂度的算法求解呢？也就是说，是否全部的“NP类问题”都属于“P类问题”呢？这就是著名的“NP=P”问题。如果答案为“是”，那就意味着“NP类问题集合”=“P类问题集合”；如果答案为“否”，那就意味着“NP类问题集合” ⊃ “P类问题集合”，但不相等。

如果“NP=P”，这个结果对我们这个世界的影响是很大的。这意味着任何一个原来找不到“P类算法”的NP类问题都可以找到相应的“P类算法”了。比如刚才说的大整数的质因数分解问题，就成为了P类问题。这意味着刚才例子中2048位的二进制大整数可以用一台普通电脑在几秒钟甚至更短的时间完成其质因数分解，那么被广泛应用的RSA加密算法就彻底失效了。我们大量的银行数字证书、网站SSL加密都不再安全，人类必须要寻找新的、更强的加密算法。

同时，这也意味着很多原来通过计算很难解决的大量问题都可以通过算法优化而轻松得到解决了。如果NP=P，那么我们就可以更好地预测天气，更容易通过氨基酸序列来预测蛋白质结构，更好的确定计算机芯片上最有效的晶体管布局，更优的完成物流交通调度，......。

如果“NP≠ P”，对我们这个世界的影响很小，或者说对实际生活几乎没有什么影响。可是，迄今为止还没有谁能给出这个证明。

这个问题的难度远远超过一般人的想象。目前，绝大多数的相关领域科学家（包括数学家、计算理论科学家、IT行业资深算法研究人员等）都认为“NP≠ P”，所以，我们可以暂时先松口气，不用太担心“NP=P”给我们日常生活带来的影响。

二、什么是NPC问题？以及第一个NPC问题

虽然我们还不知道NP是否等于P，但也不是在这方面的研究完全没有进展。早在1971年，多伦多大学计算复杂理论教授斯蒂芬·库克就在其著名论文《定理证明过程的复杂性》（《The Complexity of Theorem - Proving Procedures》）中明确提出了人们一直怀疑其是否存在的一类问题——NPC问题（NP完全问题），并给出了第一个NPC问题的证明。这对推动“ NP = P ”问题的解决是一个巨大的贡献。

第三个军械架

定理证明程序的复杂性

ACM Sympc'm

斯蒂芬·A·库克

多伦多大学

1471年5月

森马里

对某些递归的字符串集合，这个字母表，我们感兴趣的问题是找到，一个好的下界，它可能的识别时间。我们在这里没有提供这样的下界，但是定理1将给出证明(重言式！)是一个难以识别的集合，因为许多明显困难的问题可以简化为确定τ-logy。通过约简，我们的意思是，粗略地说，如果同义反复可以立即决定(通过“oraclc”)，那么这些，问题可以在多项式时间内决定。为了使这个概念更加精确，我们引入了查询机器，它类似于[1]中的图灵机。

证明了任何由多项式时间·有界不定图灵机求解的识别问题都可以“简化”为确定给定的命题公式是否为重言式的问题。“约化”的意思是，粗略地说，第一个问题可以在多项式时间内确定性地解决，前提是有一个预言器可用于解决第二个问题。从可约性的概念出发，定义了多项式的难易度，并证明了判定重言式的问题与判定两个给定的图中的第一个是否与第二个子图同构的问题具有相同的多项式度。讨论了其它例子，介绍并讨论了一种降低谓词演算证明过程复杂度的方法。

guery机器是一种多磁带图灵机，它有一种被称为guery磁带的可分辨磁带，以及三种被称为查询状态、是状态和否状态的可分辨状态。

I4a

（一）什么是NPC（NP-Complete）问题？

如果用最通俗的话来介绍，NPC问题就是NP问题中最难的那一类问题，或者说任何NP类问题的难度都小于等于NPC类问题。那么怎么定义这个“最难”呢？

如果说问题1可以在多项式时间复杂度内转换为问题2，我们就说问题2的难度大于等于问题1 。

更严格一点的描述为：设有两个问题 L₁ 和 L₂ ， S₁ 和 S₂ 分别为 L₁ 和 L₂ 的所有待验证的解的集合（就是穷举法中全部需要判断的解的集合）， l₁ 和 l₂ 分别为 L₁ 和 L₂ 的解的集合，如果存在一个多项式时间复杂度的算法能够完成的映射 f：S₁ → S₂ ，使得当且仅当 i∈l₁ 时， f(i)∈l₂ ，我们就说问题 L₁ 可以在多项式时间复杂度内转换为问题 L₂ ，称为问题 L₁ 可以归约为问题 L₂ ，记作 L₁ ∝ L₂ 。

这种归约关系显然是可传递的，也就是说，如果 L₁ ∝ L₂ 且 L₂ ∝ L₃ ，那么 L₁ ∝ L₃ 。

这种情况下，问题2如果能够在多项式时间复杂度内得到解决，或者说如果问题2是一个“P类问题”，那么问题1显然也会是一个“P类问题”。这是比较显然的，简略证明如下：

按照前面的定义，L₁ ∝ L₂ ，并设问题 L₁ 和 L₂ 的最大规模为n，映射f可以在 P₁(n) 的步骤内完成。如果 L₂ 可以在 P₂(n) 步骤内得到解决，即在 P₂(n) 步骤内可以得到 l₂ ，那么我们再用 n · P₁(n) 的步骤得到 f(S₁) ，对于使 f(S₁)中元素 属于 l₂ 的 S₁ 的子集即构成 l₁ 。因此，可以用 n · P₁(n)＋P₂(n) 的时间复杂度得到 l₁ ，也就是得到 L₁ 的解集。

由于 P₁(n) 和 P₂(n) 都是多项式，因此n · P₁(n)＋P₂(n) 也是一个多项式，即问题 L₁ 也可以通过多项式时间复杂度求解，从而 L₁ 也是一个“P类问题”。

既然我们说NPC问题是所有NP类问题中最难的那种，那么按照上述定义，也就意味着如果一个问题是NPC问题需要满足两个条件：一是它首先要是一个NP类问题；二是任何其它NP类问题都可以归约到这个问题。

由于任何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://www.bjxsw.cc），接着再看更方便。