千禧年七大数学问题之——“NP=P”

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

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

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

之所以要研究一个问题是否有多项式时间复杂度的算法，是因为多项式时间复杂度的计算量增长速度相对来说算是“慢”的，随着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 ”问题的解决是一个巨大的贡献。

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

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

如果说问题1可以在多项式时间复杂度内转换为问题2，我们就说问题2的难度大于等于问题1 。
更严格一点的描述为：设有两个问题 和 ， 和 分别为 和 的所有待验证的解的集合（就是穷举法中全部需要判断的解的集合）， 和 分别为 和 的解的集合，如果存在一个多项式时间复杂度的算法能够完成的映射 ，使得当且仅当 时， ，我们就说问题 可以在多项式时间复杂度内转换为问题 ，称为问题 可以归约为问题 ，记作 。
这种归约关系显然是可传递的，也就是说，如果 且 ，那么 。

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

按照前面的定义， ，并设问题 和 的最大规模为n，映射f可以在 的步骤内完成。如果 可以在 步骤内得到解决，即在 步骤内可以得到 ，那么我们再用 的步骤得到 ，对于使 中元素 属于 的 的子集即构成 。因此，可以用 的时间复杂度得到 ，也就是得到 的解集。
由于 和 都是多项式，因此 也是一个多项式，即问题 也可以通过多项式时间复杂度求解，从而 也是一个“P类问题”。

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

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

另外，根据归约关系的可传递性，如果某一个问题 是NPC问题，并且这个问题还可以归约到另外一个NP类问题 ，也即 ，那么 也必然是一个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) 此人当前思维的状态。

为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

（1）一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号“B”表示空白。纸带上的格子从左到右依次被编号为 0,1,2,... ，纸带的右端可以无限伸展。

（2）一个读写头 HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。

（3）一套控制规则 TABLE。根据当前机器所处的状态（相当于当前所执行的指令）以及当前读写头所指的格子上的符号来确定读写头下一步的动作，改变纸带当前格子里面的符号（如需要），并令机器进入一个新的状态（相当于确定下一步要执行的指令）。这个TABLE其实就是一套指令集，它在某种意义上就相当于我们今天计算机里面的程序。它至少包括以下内容：改写当前格子为某个符号、读写头向左或者向右移动一步、确定下一步执行的指令。

为了让大家更容易理解图灵机，举个例子吧。下图就是某个图灵机的一张控制规则TABLE，这个图灵机假设输入是只有“a”和“b”两种字符组成的字符串，它能够判断这个字符串是否是类似“aaabbb”形式的，也就是由同样数量连续个a和连续个b组成的字符串。在图灵机中，“B”表示“空”（Blank），如果后续状态是“Qaccept”或者“Qreject”，则分别表示运行结束且判断结果为“是”或“否”。

（4）一个状态寄存器。它用来保存图灵机当前所处的状态，也就是当前需要执行的指令（上图中的Q0～Q4）。

某一些指令运行完毕后，图灵机就进入了“停机状态”，这时纸带上的符号或者“Accept”、“Reject”状态就是本次运行的结果。

图灵设计的这样一台机器能模拟人类所能进行的任何计算过程。不考虑效率的前提下，今天人类的再高端的计算机的程序运算都可以通过图灵机实现。

2、非确定图灵机（NDTM，Non-Deterministic Turing Machine）

非确定图灵机与前面说的图灵机的区别在于，“控制规则TABLE”中的确定的下一步动作不是一个，而是多个。在实际运行过程中，NDTM会随机选择某一个动作继续运行下去，形成一个运行分支。因此，NDTM针对同一个输入，实际运行结果是不确定的。但是有一点需要明确，就是NDTM中不会产生矛盾，某一个输入如果某个分支给出的结果是“接受”，那么无论选择哪一条道路，最终的结果都不会是“拒绝”（这里我们没有排除某种分支下某个NDTM无限运行下去，永不停机的可能）。

3、库克定理证明思路

做了这么多铺垫，我们来开始说库克定理的证明思路。请大家千万别跳过这一部分，这是NPC问题存在的鼻祖式证明。

（1）按照NPC问题的定义，先要证明SAT问题是一个NP问题。
这个证明太显然了。要验证某个SAT问题，只需要把任意给定的n个逻辑变量的取值带入那个逻辑表达式运算一下，看结果是否为真即可。因为逻辑表达式都是基于“与、或、非”这几种运算的，这个运算过程必然是在以n为变量的多项式步骤内可以完成的。

（2）难的是这第二步，要证明任意一个NP类问题都可以在多项式时间复杂度内规约为SAT问题。
这个证明最主要难在如何处理“任意”这个条件。NP类问题无穷多种，它们唯一的共同点就是给出一个待定解，可以在多项式时间复杂度内判断是否真的是这个问题的解。库克的论文中给出了一个非常巧妙的思路，充分利用这个唯一的共同点，基于非确定图灵机的模型及其运行过程，完成对一个逻辑表达式的构造。而这个构造出来的逻辑表达式对应的SAT问题，就是被规约到的问题。
（I）对于任意一个NP类问题，既然都可以在多项式时间复杂度内完成对某个待定解的判定，那么对应这个待定解，也必然存在着一个相应的图灵机来完成这个判定过程，且这个图灵机的运行时间复杂度是多项式级的。既然该问题的每个待定解都对应着一个图灵机的判定过程，那么也就意味着存在一个非确定图灵机（NDTM），对于每个待定解，这个NDTM都存在着某个运行分支可以完成相应的判定过程。特别地，对于每个真正的解，相应的NDTM运行分支一定会给出“接受”的结果。
（II）由于对任意一个NP类问题，相应的NDTM是确定的，显然其控制规则TABLE也是确定的。而且，对于NDTM的每个运行分支，都有一条确定的运行路径。
我们假设类似上图的TABLE表中有t行状态，分别为{Q0, Q1, Q2, ......, Qt}，我们设第i步的状态为 {Q0, Q1, Q2, ......, Qt}；又因为这个NDTM至多运行P(n)步（P(n)是n的某个多项式函数），因此至多纸带上有P(n)+1个格子被读写，于是我们设初始输入为 ，第i步的时候纸带上的字符集合为 ，这里每个 的长度都是P(n)+1 。
于是，NDTM的每个运行分支都会形成一组确定的（ ）序列。如果序列的最后一个 状态是“Accept”，就说明输入 是这个NP类问题的解。
（III）核心步骤到了：如果某个输入 是那个NP类问题的解，就意味着至少存在一个按照上述定义确定的、符合这个NDTM运行逻辑规则的（ ）序列，且其 状态是“Accept”；反过来，如果我能找到一个按照上述定义确定的、符合这个NDTM运行逻辑规则的（ ）序列，且其 状态是“Accept”，那么这组序列的初始输入 就必然是那个NP类问题的解。
剩下的事就是构造一个逻辑表达式，使得这个逻辑表达式得到满足的时候，就对应着一个符合这个NDTM运行规则的（ ）序列，且其 状态是“Accept”。由于图灵机运行规则的确定性，这个逻辑表达式显然存在，且其构造不能用“难”来形容，而应该用“复杂”来形容，需要细致、认真、准确的态度和基本的逻辑能力。本文就不赘述了，有兴趣的可以参看相应专业的参考书。
（IV）既然我们构造出了一个逻辑表达式，一旦这个逻辑表达式被满足了（这正好是一个SAT问题），就意味着那个NP类问题有解了，那么显然那个NP类问题已经被规约到了一个SAT问题。而且，构造过程其实就是NDTM这个分支的运行过程，其时间复杂度当然是多项式级别的。由此，库克证明了任意NP类问题都可以在多项式时间复杂度内规约为一个SAT问题。

三、其它已经发现的NPC问题

“SAT问题”是在1971年由库克发现的第一个NPC问题。在之后的1972年，理查德·卡普将这个想法往前推进，发表了他著名的论文“Reducibility Among Combinatorial Problems”，在里面提出并证明了21个NPC问题。这些被证明为NPC的问题都是比较有名的组合数学与图论等方面的问题，包括“0-1整数规划”、“集合覆盖”、“哈密顿循环”、“3-SAT”问题、“背包问题”、“三位匹配问题”等等。

其中“哈密顿循环”演化而成的比较著名的一个问题叫做“推销员问题”，是说某个推销员要走访n个城市，每两个城市之间的距离都给出了，推销员从某给定的城市出发，要求每个城市走访一次后再回到出发城市，那么怎么安排走访顺序使得总行程最短？

这个问题在n的多项式时间复杂度内目前是无法求解的。如果用最笨的穷举法，总共可能的顺序有(n-1)!种情况，每种情况还需要计算n-1次加法，其时间复杂度为O((n-1)*(n-1)!) = O(n!)。当然，经过优化，肯定存在更理想的算法，比如通过动态规划精确算法，可以达到的时间复杂度为O( )。

四、关于NP是否等于P

2010年8月6日，HP LAB的 Vinay Deolalikar 教授宣布证明了 ，在他的主页上证明过程已经公布（PDF格式共103页），但在8月15日，专家学者对论文的看法基本达成共识，那就是证明不能成立。

时至今日，还没有哪位学者能够给出确定性的结论，但是计算复杂度理论的学者普遍认为 。

当然，从非证明的角度来看这个问题的话，存在那么多个NPC问题，只要有一个能够找到多项式时间复杂度的算法，那么NP=P就成立了，可是50多年下来，一个都没有找到，这也从反面说明了 的可能性很大。

我还看到过更具情感色彩的观点。麻省理工学院的科学家Scott Aronson在一篇博文中提出了10个 的理由，我把第9个理由的大致内容记述在这里：如果NP=P，那么“创造性的飞跃”将没有特殊价值，在解决问题与认可解决方案之间没有根本的隔阂，任何能欣赏交响乐的人都是莫扎特，每个能看懂一步一步的数学证明的人都是高斯，每个能认识到好的投资策略的人都是巴菲特。

也许正是由于NP=P会使这个世界太过于无趣，所以上帝不允许这样的事情发生。