P和NP那些事

在计算机科学里，有时间复杂度的概念，然后就有P,NP,NPC,NP-hard的概念，平常大家说的这个题是np的，只能搜了，其实是理解错了np的概念，首先要明确np并不是“不是p”的意思，p大家都清楚是指有多项式时间的算法，而np看全称是“nondeterministic polynomial time”，是说非确定多项式时间，进一步说，正如图片上说的p是属于np的，所有p问题都是np问题。

ok，下面仔细说一下，按照官方的解释呢

p是指在多项式时间能由确定型图灵机解决的问题

np是指在多项式时间能由非确定型图灵机解决的问题

确定型图灵机可以理解为就是按照某种固定的算法，一步步求出解的程序，而非确定型图灵机其实是概念上的，他的理论价值更大一些，他是指某个程序rp非常好，能猜出答案。怎么叫猜出答案呢，举个例子比如说哈密顿问题（是说经过图上的所有点一次且仅一次的路径），程序猜出了个路径ACDEFB啥的，然后程序要自己看看这个路径是不是哈密顿路，验证了一下，我勒个去，还真是，于是答案就出现了。所以这里的猜是指给出一个正确的答案，就是不仅猜出了个答案，还要自己验证一下是不是正确的，所以在有些地方解释np就是说能在多项式时间验证的问题就是np的，也不能说不对吧。

我们看到p是属于np的，那么是不是有是np但不是p的问题呢，也就是p是否等于np呢，这是个亘古难题，但是大家普遍倾向于不等于。

这里有点跳跃啊，我们先要介绍一个规约的概念，规约就是说一个问题A可以在多项式时间转化为问题B，然后问题A有解当前仅当转化后的问题B有解，也就是说只要解决了B那么就可以解决A，注意这个转化是单向的，比如你可以用解二次方程的方法解一次方程，但是反过来却不行。

然后有个叫Cook的人发现所有的np问题都可以规约到一种叫做SAT的问题，也就是说只要SAT能有效的解决，所有问题都能利这种方法经过相应转化而有效解决，后来人们发现所有的问题能规约到的问题不止一种，而是一大类，有很多个，这类问题就被称作NP-complete问题，俗称np完全问题，就是说这类问题是np里最难的，所有的np问题都可以规约到他们。到这里我们注意到npc问题是有两个条件的：

（1）他是np问题

（2）所有的np问题都可以规约到他。

如果只满足条件（2）那么被称作NP-hard，俗称np难问题，也就是说NP-hard和np问题的交集就是npc，那么以后要证明某个问题是npc问题只要先证明他是np问题，再证明某个npc问题可以规约到他（注意这个顺序是某npc规约到你要求的问题，很多人都犯顺序的错误）就可以了，如果你证明了某个问题是npc的，那么你就不用费劲心思的去想优雅的多项式算法了。

好了，让我们看看传奇的第一个npc问题SAT到底是什么，SAT全称是satisfiability，他是问对于一个合取范式，是否有一种输入使得他的输出是1，具体点就是类似这样的布尔表达式（x1 or x2 or x3）and(x3 or x4)and(x1 or x5)对于所有的x是否有一种01取值，使得最后的结果是1，据说证明这个是npc非常复杂，大体思想就是说给定输入的图灵机操作都可以表示成这种形式的布尔表达式。而对于acmer比较熟悉的2-SAT问题就是SAT的特例，并且他是有多项式算法的，就是2-SAT是p的，而3-SAT就是npc问题了。

npc问题有很多的，比较有名的有团问题，顶点覆盖集问题，支配集问题，独立集问题，哈密顿路问题，旅行商问题等，同样有很多是NP-hard而不是npc的问题，比如围棋，停机问题等。

前一段时间比较火的就是一位HP的研究员Vinay Deolalikar声称证明了P≠NP，但是后来被证明是错误的╮(￣▽￣”)╭ ，不过我感觉这个可能和哥德巴赫猜想一样，按照哥德尔不完备定理来说，在现有理论的体系下，可能无法证明，需要利用到理论体系之外的东西，当然我也只是猜测，至于到底怎么样我们还是静观其变吧。