什么是P问题?NP问题?NPC问题?三者关系如何?
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/27 11:50:43
什么是P问题?NP问题?NPC问题?三者关系如何?
什么是P问题?NP问题?NPC问题?三者关系如何?
什么是P问题?NP问题?NPC问题?三者关系如何?
1、P问题
P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出.如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数,则我们说这种可以在多项式时间内解决的判定性问题属于P类问题.P类问题就是所有复杂度为多项式时间的问题的集合.
NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解;P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.
2、NP问题
然而有些问题很难找到多项式时间的算法（或许根本不存在）,比如找出无向图中的哈米尔顿回路问题,但是我们发现如果给了我们该问题的一个答案,我们可以在多项式时间内判断这个答案是否正确.比如说对于哈米尔顿回路问题,给一个任意的回路,我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）.这种可以在多项式时间内验证一个解是否正确的问题称为NP问题.显然,所有的P类问题都是属于NP问题的,但是现在的问题是,P是否等于NP?这个问题至今还未解决.
NP这个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解.
3、NP完全问题
此外请注意,NP问题不一定都是难解的问题,比如,简单的数组排序问题是P类问题,但是P属于NP,所以也是NP问题,你能说他很难解么?刚才说了,现在还不知道是否有P=NP或者PNP,但是后来人们发现还有一系列的特殊NP问题,这类问题的特殊性质使得很多人相信PNP,只不过现在还无法证明.这类特殊的NP问题就是NP完全问题（NPC问题,C代表complete）.
NP完全问题是求NP中判定问题的一个子类.NPC问题存在着一个令人惊讶的性质,即如果一个NPC问题存在多项式时间的算法,则所有的NP问题都可以在多项式时间内求解,即P=NP成立!这是因为,每一个NPC问题可以在多项式时间内转化成任何一个NP问题.比如前面说的哈米尔顿回路问题就是一个NPC问题.NPC问题的历史并不久,cook在1971年找到了第一个NPC问题,此后人们又陆续发现很多NPC问题,现在可能已经有3000多个了.所以,我们一般认为NPC问题是难解的问题,因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法,这太不可思议了,但是也不是不可能）.类似哈米尔顿回路/路径问题,货郎担问题,集团问题,最小边覆盖问题（注意和路径覆盖的区别）,等等很多问题都是NPC问题,所以都是难解的问题.