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或者P<>NP,但是后来人们发现还有一系列的特殊NP问题,这类问题的特殊性质使得很多人相信P<>NP,只不过现在还无法证明。这类特殊的NP问题就是NP完全问题(NPC问题,C代表complete)。
NP完全问题是求NP中判定问题的一个子类.NPC问题存在着一个令人惊讶的性质,即如果一个NPC问题存在多项式时间的算法,则所有的NP问题都可以在多项式时间内求解,即P=NP成立!!这是因为,每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久,cook在1971年找到了第一个NPC问题,此后人们又陆续发现很多NPC问题,现在可能已经有3000多个了。所以,我们一般认为NPC问题是难解的问题,因为他不太可能存在一个多项式时间的算法(如果存在则所有的NP问题都存在多项式时间算法,这太不可思议了,但是也不是不可能)。类似哈米尔顿回路/路径问题,货郎担问题,集团问题,最小边覆盖问题(注意和路径覆盖的区别),等等很多问题都是NPC问题,所以都是难解的问题。
分享到:
相关推荐
关于P是否等于NP是一个存在了很久的问题,这里不做讨论。 通俗的理解这两个问题的话:在借助计算机的前提下。P问题很容易求解;NP问题不容易求解,但对于某一答案我们可以很快验证这个答案是否正确。 3.NPH...
[总结]算法中的P问题、NP问题、NP完全问题和NP难问题 - CSDN博客.html
NP完全问题的概述,包括P类、NP类、CNP类问题的介绍。
在计算复杂性理论中,旅行商问题是NP类中的典型问题。 借助一种名为“最大删除法”的全新方法,为其构造了一... 由于这个问题也是NP完全的,因此必然证明P = NP是正确的。 它表明了著名的“ P vs NP”开放问题的破解。
NP完全问题(NP-C问题),是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是 NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P。
本文档对NP完全问题详细解释,举了很多的例子 NP完全问题(NP-C问题),是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是 NP=P?,问题就...
第10章 NP完全问题学习要点:确定算法和不确定算法判定问题和最优化问题的关系可满足性问题P类问题和NP类问题典型的NP完全(或NP难度)问题的证明章节内容:1
三维匹配问题是NP完全的 首先,很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n,且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的,可以通过3-SAT≤p\leq_p≤p三维匹配证明。 【3-SAT≤p\...
证明哈密顿圈问题是NPC的,可以通过证明3-SAT≤p\leq_p≤p哈密顿圈来得到。 【3-SAT≤p\leq_p≤p哈密顿圈】 构造方法如下: (1)对于每一个变量xix_ixi,创建3m+3个顶点。命名为vi,1,…,vi,3m+3v_{i,1},…,v_{i,...
(1)猜测阶段 (2)验证阶段 (1)P类问题可以用多项式时间的确定性算法来进行判定或求解 (2)NP类问题可以用多项式时间的非确定性算法来进行判定或求解 (1
P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困 难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个...
对类P是类NP的真子集猜测的第二证明,徐万东,,判定一个任意的无向可平面图G是否是哈密顿图问题是六个重要的NP完全问题之一(HC)。本文根据判定除马图以外的任意无向图是否是哈密��
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最...
通过展示我们如何“编程”市场以解决NP完全问题,我也证明了相反的观点。 由于P可能不等于NP,所以市场可能效率不高。 具体而言,随着时间序列延长或变得越来越频繁,市场变得效率越来越低。 通过基于数据可用性对...
对类P是类NP的真子集猜测的证明,徐万东,,可平面图的可三着色性(P3C)是一个NP---完全问题。在用计算机判定一个可平面图是否可以三着色时,会产生第二类设定颜色错误。此时�
引入了nP投射模和强P投射模的概念,并证明了M是nP投射模当且仅当M是Pn预包络f:A→B的余核,其中B是投射模;如果R是左凝聚右完全环,那么(PP,PP⊥)是完备的余挠理论,(SPP,SPP⊥)是完备遗传的余挠理论,其中PP表示P投射...
3 不可解问题 2 .3 P 类问题和 NP 类问题 2 .3 .1 判定问题 2 .3 .2 确定性算法与 P 类问题 2 .3 .3 非确定性算法与 NP 类问题 2 .4 NP 完全问题 2 .4 .1 问题变换与计算复杂性归约 2 .4 .2 NP 完全问题的定义 2 .4...
用Python编写的该算法至少可以在n ^ 3的时间内解决汉密尔顿电路问题的一个子集,该子集是NP完全的。
书名:算法设计与分析 作者:王晓东 图书目录 第1章 算法引论 1.1 算法与程序 1.2 表达算法的抽象机制 1.3 描述算法 1.4 算法复杂性分析 ...第8章 NP完全性理论 ...8.4.5 子集和问题 8.4.6 哈密顿回路问题
A. NP问题都是不可能解决的问题 B. P类问题包含在NP类问题中 C. NP完全问题是P类问题的子集 D. NP类问题包含在P类问题中29. 蒙特卡罗算法