1、引子
2000年，美国克莱数学研究所公布了世界七大数学难题，又称千禧年大奖难题。其中P-NP问题被列为这七大世界难题之首，从而大大激发了对这一问题的研究热情。
P-NP问题是什么？为什么说它难呢？
今天，已经在围棋上毫无争议的战胜了人类，让人类棋手不禁黯然神伤。这个被誉为人类智慧巅峰的棋类游戏吸引着无数高手的挑战。那么围棋的难度究竟如何？怎么度量呢？机器算法战胜了人类棋手，是否就预示着机器的万能呢？
这些问题的背后都涉及到一个终极问题：我们这个世界究竟是由一些什么样的问题组成的？以及如何度量这些问题的难易程度？
如果用计算的眼光去看，或许能够得到一些启示。
2、什么是计算
我可以首先给出一个比较时髦的对计算概念的理解：
广义上讲，一个函数变化如把x变成了f(x)就是一个计算！如果我们把一切都看作是信息，那么更精确的讲，计算（）就是关于信息的变换（ of ）！
如果采用这种观点，你会发现，其实自然界充满了计算！如果我们把一个小球扔到地上，小球又弹起来了，那么大地就完成了一次对小球的计算。因为你完全可以把小球的运动都抽象成信息，它无非是一些比如位置、速度、形状等等能用信息描述的东西嘛，而大地把小球弹起来就无非是对小球的这些信息进行了某种变换，因而大地就完成了一次计算！你可以把整个大地看作是一个系统，而扔下去的小球是对这个系统的输入，那么弹回来的小球就是该系统的输出，因而也可以说，计算就是某个系统完成了一次从输入到输出的变换！
现实世界充满计算！完全可以把所有的自然界存在的过程都抽象成这样的输入输出系统，所有的大自然存在的变量都看作是信息，因而计算无处不在！正因为这样，DNA计算机、生物计算机、量子计算机这些东西层出不穷，因为DNA的化学反应、量子世界的波函数变换都是可以看作是计算。
然而，从计算机科学的角度看，研究计算最重要的武器还是图灵机，因为图灵机是一个理论计算机模型，它最主要的能耐就在于对计算的刻画上！
关于图灵机的描述，可以参考：《》。
有了图灵机模型，科学家才能严肃形式的定义一个问题的复杂程度。
3、P问题和NP问题
我们经常会在网上看到“这个问题很难，是NP问题吗，只能用穷举法了”、“一个问题要么是P问题、要么是NP问题”之类的话，显然是对P-NP问题的不理解。而我们的教科书上同样也是充满着大量的术语和公式，加上P-NP概念在命名时候的历史问题，使得绝大多数的人都对P-NP类问题望而却步，要么就是人云亦云。
实际上，大多数人所说的NP问题其实都是指的NPC问题，NP问题并不是那种“只有穷举才行”的问题，NPC问题才是，至少目前是。
下面我就来好好讲讲这个基本概念。
先要简单说明一下时间复杂度（Time ）这个概念，它是衡量一个问题在计算上难以程度的一个基本指标。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长的多快程度。也就是说，对于一台计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样变化，是跟着变慢了数百倍呢？还是变慢了数万倍？这在计算机科学中尤为重要。
我们把前面的几种复杂度分为两个级别，第一个级别的复杂度远远小于第二个级别的：
当我们在求解一个问题时，当然会选择多项式级的复杂度的算法是，因为非多项式级的复杂度需要的时间太多，一旦问题的规模上去，求解所化的时间往往不能忍受，比如说10年。
自然地，我们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。甚至有些问题根本不可能找出一个正确的算法，这称之为“不可判定性问题”(Un- )。例如停机问题（The ）就是一个著名的不可解问题。再比如，输出从1到n这n个数的全排列。不管你用什么方法，你的复杂度都是阶乘级，因为你总得用阶乘级的时间打印出结果来。
在比如“回路问题”：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后又走回来的路（满足这个条件的路径叫做回路）。这个问题现在还没有找到多项式级的算法。事实上，这个问题就是我们后面要说的NPC问题。
好了，有了上面的基础，我们下面就来引入P问题和NP问题的定义。
P类问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。
P是英文单词多项式（）的第一个字母。哪些问题是P类问题呢？通常信息奥赛NOI、NOIP和ACM比赛中的赛题大都属于P类问题。原因很简单，一个用穷举换来的非多项式级时间的超时程序很难体现出一个选手的智慧和价值，当然也就不会涵盖任何有价值的比赛算法。
而NP问题（ time ）的概念就有点难以理解了停机问题，或者说容易理解错误。原因很简单，NP问题不是非P类问题。它的定义是从另一个层面上进行的：
简单来说，NP问题是指可以在多项式的时间里验证一个解的问题。
参照前面P问题的定义，这里需要特别之处的是：P问题的定义是从找一个解的问题的角度出发的；而NP问题是从验证一个解的角度出发的。
这也是为什么容易将他们误解的根本原因。至于为什么会这样，其背后有着非常多的历史故事和历史原因。而正是因为这样的差别，才引出了开篇P-NP问题，甚至是更高层的哲学问题：
究竟是求解一个问题难呢？还是验证一个问题的解是否正确的问题难呢？
直觉告诉我们，应该是验证一个问题的解是否正确比较容易。例如回路问题，验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把一条路径的长度加出来。只要运气够好，猜得准，就能在多项式的时间里解决这个问题。这就是NP问题。
当然，既然有NP问题，自然也就有非NP问题了，即co-NP问题。比如，虽然你猜到了解，但是没有用，因为你不能在多项式的时间里去验证它。举个例子来说，有一个这样的问题：一个图中是否不存在回路。这个问题就没有办法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有回路”。因此，回路是NP问题，而这个问题则不是。
为什么NP问题要这样定义呢？这是因为通常只有NP问题才可能找到多项式的算法。直觉告诉我们验证一个问题的解比求解一个问题要简单，我们不会指望一个连多项式去验证一个解都不行的问题会存在一个解决它的多项式级的算法。虽然有些拗口，但事实也确实如此。
读到这里，相信大家明白了，计算机科学中的号称最困难的“NP问题”实际上是在探讨NP问题与P类问题的关系。
4、P问题和NP问题的不同视角
有了上面关于P问题和NP问题的基本概念，下面我们再从不同的角度进行一下考察，帮助我们进行深入的理解。
实际上，如果我们去看计算机理论方面的教科书或文献，会发现P-NP问题的定义形式还是非常多的，我们这里归纳了一下，大致可以分为三种。
（1）穷举搜索角度：求解问题与验证答案
也就是我们上面的定义方法。这个是最自然的方法，因为计算机科学中的很多问题一开始都是倾向于求解各种搜索问题的。比如解线性方程组、求图的生成树、求旅行商问题的最短路径等。
因此，P问题就被定义为能够高效（多项式时间内）求解的搜索问题；而NP问题则是能够高效（多项式时间内）验证解的搜索问题。
如果容易验证一个给定的答案是否为一个问题的正确解，那么这个问题的求解是否也容易呢？简单来说，高效的验证是否意味着高效的求解呢？直觉告诉我们，有些问题应该可以，有些问题则很难。
（2）判定角度：证明与验证
我们从教科书中还经常看到这样的一种论述：围绕一个判定问题来对P-NP问题进行定义。这类描述通常是在偏数学的资料中，因为在数学中判定问题是对搜索问题的一种简化，同时能够更加方便地进行证明与推理。判定一个给定的论断（例如布尔表达式）是否满足预先定义的性质（例如可满足性）本身也构成了一类在数学中有趣而重要的问题。例如SAT问题。
因此，从这个角度出发，P问题就被定义为能够高效（多项式时间内）求解的判定问题；而NP问题则是能够高效（多项式时间内）验证证明系统的判定问题。
（3）图灵机求解角度
这个算的上是计算机科学中最严肃而形式化的方式了。
简单来说，在确定性图灵机下能用多项式求解的问题就是P类问题，而在非确定性图灵机下能用多项式求解的问题就是NP问题。
5、关于P是否等于NP的论断
很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的NP问题都是P类问题。
我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中，把所有 NP问题划进另一个集合NP中，那么，显然有P属于NP。现在，所有对NP问题的研究都集中在一个问题上，即究竟是否有P=NP？通常所谓的“NP问题”，其实就一句话：证明或推翻P=NP。
NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在计算机科学研究中，这是一个耗费了很多时间和精力也没有解决的终极问题，好比物理学中的大统一和数学中的歌德巴赫猜想等。
康德说过：直觉和概念构成了我们掌握的所有知识，所以仅有概念而没有相应的直接，或仅有直觉而无概念，都不能产生知识。
这段话给我们的启发是，所谓在包含正确知识体系的科学中，产生概念的哲学因素和产生直觉的经验因素都很重要。
从哲学的角度看，P问题和NP问题都有很强的概念性，求解一个问题和验证一个答案的难以程度应该是不同的，后者应该容易得多。
从经验的角度看，NP问题中的一部分难题，迄今为止，人类尚未找到高效的求解算法，而这些问题又是来源于不同学科和不同时期，这些本质上相互独立的研究，似乎也预示着这类问题的困难程度肯定不是巧合。
人们如此坚信P≠NP还有一个另外的原因，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题（NP-），也即所谓的 NPC问题。正是NPC问题的存在，使人们相信P≠NP。一旦你理解了NPC问题，你就会觉得NPC问题使P=NP变得多么不可思议。
但是，如果P = NP，则意味着只要能验证一个事物，我们就能解决它，这将是一个多么有吸引力的事情呀。P是否等于NP这个问题的魅力就在于，究竟是否所有的问题都将变得易如反掌呢？还是说有些事情注定就是没有简单的解决办法？无论如何，美好的世界总会让人无限的憧憬。
6、NPC问题
为了说清楚NPC问题，我们先引入一个重要的概念：规约化（）。
简单地说，一个问题A可以规约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。
《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以规约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。
同样地，我们可以说，回路可以规约化为TSP问题（ ，旅行商问题）：在回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题规约化为在TSP问题中，是否存在一条长为0的路径。回路存在当且仅当TSP问题中存在长为0的回路。
“问题A可以规约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决，倘若B的时间复杂度比A的时间复杂度还低了，那A的算法就可以改进为B的算法，两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者。
很显然，规约化具有一项重要的性质：传递性。如果问题A可以规约化为问题B，问题B可以规约化为问题C，则问题A一定可以规约化为问题C。
现在再来说一下规约化的标准概念就不难理解了：如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可以规约化为问题B。
需要强调的是，我们所说的“可规约化”是指的可“多项式地”规约化（-time ），即变换输入的方法是能在多项式的时间里完成的。规约化的过程只有用多项式的时间完成才有实际意义。
好了，从规约化的定义中我们看到，一个问题规约化为另一个问题停机问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断规约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题，联想起规约化的传递性，自然地，我们会想问，如果不断地规约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案是肯定的！
也就是说，竟然存在这样一个NP问题，所有的NP问题都可以规约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC 问题，也就是NP-完全问题。
NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是NP问题中最复杂的问题。因此，我们可以看到，人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。到此，我们基本上把NP问题和NPC问题区别开了。
NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。
既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”（目前已经发现了四千多个NPC问题了）。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它，这样就可以说它是NPC问题了。这里我们不禁会好奇的问：那么第一个NPC问题时什么呢？这就是著名的逻辑电路问题。
7、逻辑电路问题
逻辑电路问题是NPC类问题的“鼻祖”。其它的NPC问题都是由这个问题约化而来的。逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为True。
什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻的线组成。看看下面的图你就会马上就明白了。
这是个较简单的逻辑电路，当输入A、输入B、输入C分别为True、True、False或False、True、False时，输出为True。
那么问题来了，给定一个逻辑电路，是否存在一种输入使输出为True呢？这就是逻辑电路问题。
逻辑电路问题属于NPC问题。这是有严格证明的，证明过程相当复杂，这里就不详细说了。1971年， Cook发现并证明了第一个NPC问题后，目前人类已找到了数千个这样的问题。Cook随后也因为这个极其重要的研究型工作被授予图灵奖。
我们再举几个有趣的例子。魔方，即便是3*3*3的小魔方，一般人也好话费不少功夫来复原，而求解更大魔方可想而知，但魔方的难度实际上是个P问题，这也就是为什么一旦少数人掌握了其中的奥秘，可以用让人惊叹的速度恢复；而俄罗斯方块、扫雷和数独等游戏则都是NPC类问题。
而双人对战的棋类，包括国际象棋、跳棋、黑白棋和围棋等，对的，包括围棋，这些游戏的大规模版本的难度至少不亚于NPC类问题，而且这些双人棋类游戏又不属于NP类问题。比如如果告诉你，最后是白方赢，或者第三列的卒吃王，你根本就没有办法验证这样的结果。所以，我们一般认为，这类棋类游戏的难度均大于任何NP类问题。
8、NP-Hard问题
再来说一下NP-Hard问题。NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条。也就是说，NP-Hard问题要比 NPC问题的范围广。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题，即验证一个问题的解的都要花费超过多项式的时间。因此，即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。
比如一个具体的围棋问题。要保证每局都能赢的话，传统的方法需要电脑穷举出所有的可能性，并根据每一步棋的变化搜索出最终达到胜利的下棋路径，而围棋的状态空间复杂度达到了10的172方，而围棋的博弈树复杂度达到了10的300次方，光看数字可能不直观，一句话就是围棋的变化多过宇宙的原子数量！即便是人类棋局这样小规模的计算，计算机都是无法完全胜任的。的胜利只能说明人类发明的近似算法比当下人类的大脑算法要好，仅此而已。
9、不可判定问题
最后再来回头来说说前面提到过的不可判定性问题。首先要说明的是，不可判定性问题对计算机的日常使用实际上是没有太大的影响。原因有两个：一是可判定性问题时少数，而且即便一个问题是可判定的，如果是NPC问题，还是意味着计算机解起来很难；二是实际上我们在大部分时间里都能很好的近似解决不可判定性问题。例如，即便我们无法证明一个程序是否有存在Bug（这也是一个不可判定性问题），我们还是可以通过各种测试方法找到其中的大部分Bug。
10、结束语
P是否等于NP，属超级难题，一直未解。不少人声称已解决该难题，但未被认可。关于P对NP问题，目前有三种观点：
第一类是主流。目前学术界普遍认为，彻底解决P和NP的关系问题还有遥远的距离。然而，而从历史上看，某个高难度的问题突然被人发现具有美妙的算法的事例还是时有发生的。最典型的就是两位印度科学家找到了关于质数判定的多项式时间算法，而这样的算法在他们之前一直被认为是不太可能的。
参考文献：
限时特惠:本站持续每日更新海量各大内部创业课程，一年会员仅需要98元，全站资源免费下载
点击查看详情
站长微信:Jiucxh
