转载:

当我们遇到一个问题时,我们总是很自然的开始恩考求解这个问题的算法.我们大多数人都没有注意到问题本身的可解性.其实很多问题很难想出一种有效算法的,当然,遍历算法除外.如果我们有一台超强的计算机,那么一切算法都是没有意义的,因为一切问题都可以用遍历来解.

算法的效率其实正是体现在问题的大规模输入上,所以,我们在比较算法的好坏时,通常考虑它在大规模输入时的运行时间,占用空间等.P与NP问题正是源自算法执行的效率.

我想绝大多数学计算机的人都听过P与NP问题,但我觉得,真正能说出它是怎么回事的,不在多数.至少在我仔细看资料之前,我是说不出P与NP问题到底是怎么回事,以及怎么证明一个问题是NP或NP完全的.所以,我想写一些自己对P与NP问题的理解.

在介绍P与NP之前,我想先介绍两个概念.

1.确定性算法

设A是求解问题B的一个算法,如果在展示问题B的一个实例时,在整个执行过程中每一步都只有一个选择,则称A是确定性算法.因此如果对于同样的输入,实例一遍又一遍地执行,它的输出从不改变.

通常我们在写程序时,用到的都是一些确定性算法,比如说排序算法,最优化算法等.

2.不确定性算法

一个不确定性算法由下列两个阶段组成.

猜测阶段:在这个阶段产生一个任意字任串Y,它可能对应于输入实例的一个解,也可以不对应解.事实上,它甚至可能不是所求解的合适形式,它可能在不确定性算法的不同次运行中不同.它仅仅要求在多项式步数内产生这个串.

验证阶段:在这个阶段,一个确定性算全证两件事.首先,它检查产生的解串Y是否有合适的形式,如果不是,则算法停下并回答NO;另一方面,如果Y是合适形式,那么算法继续检查它是否是问题实例X的解,如果它确实是实例X的解,那么它停下并且回答YES,否则它停下并回答NO.我们也要求这个阶段在多项式步数内完成.

可能很多人会认为随机算法是一种不确定性算法.其实随机算法也是一种确定性算法,因为它的随机性也是通过在输入中加入一个用于产生随机值的串实现的,同样的串得到的随机值相同.

下面给出P与NP的定义:

P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出;
NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解;

P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.NP这
个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解.

NP完全问题

NP完全事实上表求NP中判定问题的一个子类.这类问题也是很有趣的,即如果它们中的一个被证明
是多项式时间内确定性算法可解,那么所有属于这一类的其它问题也是多项式时间内确定性算法可解.

多项式时间归约:

设A和B是两个判定问题.如果存在一个确定性算法C,它的行为如下:当给C展示问题A的一个实例时,算法A可以把这个实例变换成问题B的一个实例,使得A的实例跟B的实例有相同的YES/NO应答,并且这个变换在多项式时间内完成.那么我们说A多项式时间归约到B.

事实上,我们可以将多项式时间归约看做是一个函数的映射,即F(A)=B.并且这个F是多项式时间内可计算的.也就是说问题A实现上可以通过它自身满足的条件,通过一些形式上的改变而变换到问题B.形象地讲,问题A事实上不比B难,而问题B也同样不比问题A难.

NP困难与NP完全

一个判定问题A称为是NP困难的,如果对于NP中的每个问题B,B多项式时间归约到A.
一个判定问题A称为是NP完全的,如果对于NP中的每个问题B,B多项式时间归约到A,并且A在NP类中.

NP完全问题的证明:

要证明一个判定问题是NP完全的,只要在NP完全类中找到一个问题A,将这个问题归约到待证明问题即可.要证明问题是NP完全是很困难的,因为很多问题之间的转化过程是很难想到的.第一个被证明的NP完全问题是可满足性问题,它是判定一个合取范式的布尔公式F是否存在真值指派的问题.在很多NP完全问题的证明中,我们都可以用这个问题来归约,这里不再详述.

-------------------------------------------------------------------------------------------------------------------------------

首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质。比如对于排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O(n^2)，快速排序平均情况下是O(nlgn)等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。
为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A到B是否有长度为1的路径？从A到B是否有长度为2的路径？。。。从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。注意，NP问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，你能说他很难解么？刚才说了，现在还不知道是否有P=NP或者P<>NP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信P<>NP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是难解的问题。