NP完全问题_百度百科
NP完全问题
NP完全问题(NP-C问题)，是之一。 NP的英文全称是Non-deterministic Polynomial的问题，即复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。
在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。
生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数13,717,421可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你他可以为3607乘上3803，那么你就可以用一个袖珍计算器容易验证这是对的。人们发现，所有的完全非确定性问题，都可以转换为一类叫做满足性问题的问题。既然这类问题的所有可能答案，都可以在内计算，人们于是就猜想，是否这类问题，存在一个确定性算法，可以在多项式时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。 不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文·考克于1971年陈述的。
美国麻州的克雷（Clay）数学研究所于日在巴黎法兰西学院宣布了一件被媒体炒得火热的大事：对七个“千僖年数学难题”的每一个悬赏一百万美元。
“千僖难题”之一：P （确定性多项式算法）对NP （非确定性多项式算法）
“千僖难题”之首
“千僖难题”之二：霍奇（Hodge）猜想
“千僖难题”之三：庞加莱（Poincare）猜想
“千僖难题”之四：黎曼（Riemann）假设
“千僖难题”之五：杨－米尔斯（Yang-Mills）存在性和质量缺口
“千僖难题”之六：纳维叶－斯托克斯（Navier-Stokes）方程的存在性与光滑性
“千僖难题”之七：贝赫（Birch）和斯维讷通－戴尔（Swinnerton-Dyer）猜想
NP完全问题排在百万美元大奖的首位，足见他的显赫地位和无穷魅力。
NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
假设P ≠ NP的图解。若P = NP则三类相同。
而如果任何一个NP问题都能通过一个时间算法转换为某个，那么这个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。NP完全问题也叫做NPC问题。
有些计算问题是确定性的，比如加减
乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数的问题，有没有一个公式，把代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。
这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间
多流水线调度实际上是一个NP完全问题
内进行正确与否的验算的话，就叫完全多项式非确定问题。
完全多项式非确定性问题可以用得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。
人们发现，所有的完全非确定性问题，都可以转换为一类叫做满足性问题的问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题存在一个确定性算法，可以在多项式时间内直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。
解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。
近邻法（nearest neighbor)　推销员从某个城镇出发，永远选择前往最近且尚未去过的城镇，最后再返回原先的出发点。这方法简单，也许是多数人的直觉做法，但是近邻法的短视使其表现非常不好，通常后段的路程会非常痛苦。
插入法（insertion)　先产生连接部分点的子路线，再根据某种法则将其它的点逐一加入路线。比如最近插入法（nearest insertion），先针对外围的点建构子路线，然后从剩余的点里面评估何者加入后路线总长度增加的幅度最小，再将这个点加入路线。又比如最远插入法（farthest insertion），是从剩余的点里面选择距离子路线最远的点，有点先苦后甜的滋味。
模拟退火算法
（Recuit Algorithm) 来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，在温度T时趋于平衡的概率为e-ΔE/(kT），其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。
遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法
遗传算法是解决NP问题的一种较理想的方法
，从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。生物种群的生存过程普遍遵循进化准则，群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力是对应着一个染色体的一个数值来衡量；染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。
神经网络算法
根据一个简化的统计，人脑由百亿条神经组成 — 每条神经平均连结到其它几千条神经。通过这种连结方式，神经可以收发不同数量的能量。神经的一个非常重要的功能是它们对能量的接受并不是立即作出响应，而是将它们累加起来，当这个累加的总和达到某个临界阈值时，它们将它们自己的那部分能量发送给其它的神经。大脑通过调节这些连结的数目和强度进行学习。尽管这是个生物行为的简化描述。但同样可以充分有力地被看作是神经网络的模型。
填字游戏是一种最常见的益智纸上游戏，也是NP完全问题之一，游戏一般给出一个矩形的表格。这个表格被分割为若干个大小相同的方格，方格的颜色有白色与黑色两种。白色的方格组成一些交叉的行与列，行列的长度不等。玩家根据题目所提供的有关信息，将答案填入这些行与列之中，每个白色方格中只能填入一个字。一般地说，题目给出的每一条信息就是对应的一行或一列的线索。在行与列交叉的地方，玩家必须保证在交叉的方格中填入的字同时满足题目中对行与列的要求。
最常被引用的结果之一设计神喻。假想你有一个魔法机器可以解决单个问题，例如决定一个给定的数字是否为质数，但可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP和P ≠ NP二者都可以证明。这个结论的后果是，任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。
如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P = NP问题。这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。这实际上也是为什么NP完全问题有用的原因：若有一个算法，或者没有一个这样的算法，对于NP完全问题存在，这将用一种相信不被上述结果排除在外的方法来解决P = NP问题。P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用加上最小操作（实际上，这允许了递归函数的定义）来表达。类似地，NP是可以用存在性来表达—也就是，在关系、函数、和上排除了全域量词的二阶逻辑。多项式等级，PH中的语言对应与所有的二阶逻辑。这样，“P是NP的吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”
计算机系楼将二进制代码表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：“反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。
日，HP LAB的 Vinay Deolalikar 教授宣布证明了P!=NP，证明文章已经发送到该问题各相关领域专家手中，等待检验，在他的上，证明过程已经公布（PDF格式共103页），但在8月15日，人们关于论文的看法——即证明不能成立——已经趋于稳定（当然这不能排除大家都同时犯了错误的可能性），随后的发言越来越多地集中于更抽象的层面，并且至今仍在继续。
当今时代，在纯粹科学研究，通信、交通运输、工业设计和企事业管理部门，在社会军事、政治和商业的斗争中涌现出大量的NP问题。若按经典的纯粹数学家们所熟悉的穷举方法求解，则计算时间动辄达到天文数字，根本没有实用价值。数学界许多有经验的人认为对于这些问题根本上就不存在完整、精确、而又不是太慢的求解算法。NP=P？可能是这个世纪最重要的数学问题了。P/NP问题_百度百科
P/NP问题是在理论信息学中计算理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。 P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克(Stephen A. Cook) 和 Leonid Levin 相对独立的提出了下面的问题，即是否两个复杂度类P和NP是恒等的（P=NP?）。
复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的:
P和NP相等吗?
在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能所接受的公理独立，所以不可能证明或证否。[1] 所以P-NP问题也是Clay研究所的七个百万美元大奖问题之一。
NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的。(确切定义细节请参看NP-完全)理论计算机科学家现在相信P, NP,和NPC类之间的关系如图中所示，其中P和NPC类不交。
假设P ≠ NP的类的图解.如P = NP则三个类相同.本质上，P = NP问题问道：如果是/不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。给定一个大数Y,我们可以问Y是否是复合数。例如，我们可能问是否有非平凡的因子。回答是肯定的，虽然手工找出一个因子很麻烦。从另一个方面讲，如果有人声称答案是&对，因为224737可以整除&,则我们可以很快用一个除法来验证。验证一个数是比首先找出除数来简单得多。用于验证一个正面答案所需的信息也称为证书。所以我们的结论是，给定 正确的证书，问题的正面答案可以很快的(也就是，在内)验证，而这就是这个问题属于NP的原因。虽然这个特定的问题，证明为也在P类中(参看下面的关于&质数在P中&的参考),这一点也不明显，而且有很多类似的问题相信不属于类P。
限制到是/不是问题并没有改变问题；即使我们允许更复杂的答案，最后的问题(是否FP = FNP)是等价的。
要解决P = NP问题，NP完全的概念非常有用。不严格的讲，是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在内变换成为任何特定NP完全问题的一个特例。例如，的判定问题版本是NP完全的。所以NP中的任何问题的任何特例可以在多项式时间内机械地转换成旅行商问题的一个特例。所以若旅行商问题被证明为在P内，则P = NP！旅行商问题是很多这样的NP完全的问题之一。若任何一个NP完全的问题在P内，则可以推出P = NP。不幸的是，很多重要的问题被证明为NP完全，但没有一个有已知快速的算法。
P真的容易处理吗
上面所有的讨论假设了P表示“容易”而“不在P中”表示“困难”。这是一个在理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点：
它忽略了常数因子。一个需要101000n时间的问题是属于P的（它是的），但是事实上完全无法处理。一个需要10-100002n时间的问题不是在P中的（它是的），但是对于n 取值直到几千时还是很容易处理的。
它忽略了指数的大小。一个时间复杂度n1000属于P，但是很难对付。已经证明在P中存在需要任意大的指数的问题（参看时间等级定理）。一个时间复杂度2n/1000的问题不属于P，但对与n直到几千还是容易应对的。
它只考虑了最坏情况的。可能现实世界中的有些问题在多数时候可以在时间n中解决，但是很偶尔你会看到需要时间2n的特例。这个问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于P。
它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于P，虽然事实上它可以很快求解。这实际上是解决属于NP而还不知道是否属于P的问题的一个办法（参看RP， BPP）。
新的诸如量子电脑这样的计算模型，可能可以快速的解决一些尚未知道是否属于P的问题；但是，没有一个它们已知能够解决的问题是NP完全的。不过，必须注意到P和NP问题的定义是采用象图灵机这样的经典计算模型的属于表述的。所以，即使一个量子计算机算法被发现能够有效的解决一个NP完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类P和NP相等的证明。
计算机科学家的理论
多数计算机科学家相信P≠NP。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题]]）。进一步地，P = NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的，例如NP = 余NP和P = PH。
也有这样论证的：问题较难求解(NP)但容易验证(P)，这和我们日常经验是相符的。
从另一方面讲，某些研究者认为我们过于相信P ≠ NP，而应该也去寻找P = NP的证明。例如，2002年中有这样的声明：
倾向P≠NP的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说，以我的观点，一个很弱的论据。算法的空间是很大的，而我们只是在开始探索的起点。[ . . . ] 的解决也显示非常简单的[sic]问题可能只有用非常深刻的理论才能解决。
— Moshe Vardi，
过分依赖某种投机不是规划研究的一个好的导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。
— Anil Nerode,
更正式一些，一个决定问题是一个取一些字符串为输入并要求输出为是或否的问题。若有一个算法（譬如，或一个LISP或Pascal的程序并有无限的内存）能够在最多n^k步内对一个串长度为n的输入给出正确答案，其中k是某个不依赖于输入串的常数，则我们称该问题可以在内解决，并且将它置入类P。直观的讲，我们将P中的问题视为可以较快解决的问题。
假设有一个算法A(w,C)取两个参数，一个串w，也就是我们的决定问题的输入串，而另一个串C是“建议证明”，并且使得A在最多n^k步之内产生“是/否”答案（其中n是w的长度而k不依赖于w）。进一步假设
w是一个答案为“是”的例子，，存在C使得A(w,C)返回“是”。
则我们称这个问题可以在非决定性内解决，且将它放入NP类。我们把算法A作为一个所建议的证明的检验器，它运行足够快。（注意缩写NP代表“Non-deterministic（非确定性）Polynomial（）”而不是代表“Non-Polynomial（非多项式）。）
证明的难度
虽然百万美元的奖金和大量投入巨大却没有实质性结果的研究足以显示该问题是困难的，还有一些形式化的结果证明为什么该问题可能很难解决。
最常被引用的结果之一设计神喻。假想你有一个魔法机器可以解决单个问题，例如决定一个给定的数字是否为质数，但可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP和P ≠ NP二者都可以证明。这个结论的后果是，任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。
如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P = NP问题。[3] 这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。
这实际上也是为什么NP完全问题有用的原因：若有一个多项式时间算法，或者没有一个这样的算法，对于NP完全问题存在，这将用一种相信不被上述结果排除在外的方法来解决P = NP问题。
多项式时间算法
没人知道多项式时间算法对于NP完全问题是否存在。但是如果这样的算法存在，我们已经知道其中的一些了！例如，下面的算法正确的接受了一个NP完全语言，但是没人知道通常它需要多久运行。它是一个算法当且仅当P = NP。
// 接受NP完全语言的一个算法子集和。
// 这是一个多项式时间算法当且仅当P=NP。
// “多项式时间”表示它在多项式时间内返回“是”，若
// 结果是“是”，否则永远运行。
// 输入：S = 一个自然数的
// 输出：&是& 如果某个S的子集加起来等于0。
// 否则，它永远运行没有输出。
// 注意: &程序数P& 是你将一个P写为二进制，然后
// 将位串考虑为一个程序。
// 每个可能的程序都可以这样产生，
// 虽然多数什么也不做因为有语法错误。
FOR N = 1...infinity
FOR P = 1...N
以S为输入运行程序数P N步
IF 程序输出一个不同的整数的列表
AND 所有整数都在S中
AND 整数的和为0
OUTPUT &是& 并 停机
若P = NP，则这是一个接受一个NP完全语言的算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。
可能我们想要“解决”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的IF语句替换成下面的语句：
IF 程序输出一个完整的数学证明
AND 证明的每一步合法
AND 结论是S确实有（或者没有）一个和为0的
OUTPUT &是& （或者&不是&如果那被证明了）并停机
更难的问题
虽然是否P=NP还是未知的，在P之外的问题是已经知道存在的。寻找国际象棋或围棋最佳走法（在n乘n棋盘上）是完全的。因为可以证明P ≠ EXPTIME（指数时间），这些问题位于P之外，所以需要比更多的时间。判定Presburger算术中的是否为真的问题更加困难。Fischer和Rabin于1974年证明每个决定Presburger命题的真伪性的算法有最少2^(2^(cn))的运行时间，c为某个常数。这里，n是Presburger命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如。它们无法在任何给定时间内解决。
P=NP问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有P中的语言可以用加上最小不动点操作（实际上，这允许了的定义）来表达。类似地，NP是可以用存在性来表达—也就是，在关系、函数、和上排除了全域量词的二阶逻辑。多项式等级，PH中的语言对应与所有的二阶逻辑。这样，“P是NP的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？”
计算机系楼将二进制代码表述的“P=NP?”问题刻进顶楼西面的砖头上。如果证明了P=NP，砖头可以很方便的换成表示“P=NP！”。[4]
康奈尔大学的Hubert Chen博士提供了这个玩笑式的P不等于NP的证明：“。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到矛盾。
公元2010年：
8 月 6 日，HP LAB的 Vinay Deolalikar 教授宣布证明了P!=NP，证明文章已经发送到该问题各相关领域专家手中，等待检验，在他的主页上，证明过程已经公布（PDF格式共103页）。
8 月 8 日，Lipton 在博客上讨论了这篇论文，给出了略显乐观的评价：这是一个值得认真对待的证明。这篇文章引来大量严肃的学术性回复，大多来自业内人士，各方看法不一。
8 月 9 日，Lipton 在参考各方反应的基础上同 Ken Regan 合写了一篇新的，指出了 Deolalikar 证明思路中的一些重大漏洞，对它的整体评价口吻较前日明显低调了许多。
同日，因为 Lipton 博客文章后面大量有价值的评论值得梳理，Venkatasubramanian 建立了一个可以被公众编辑的 Google Docs 文档以整理这些讨论。翌日，在陶哲轩的帮助下，该文档被转换成一个 wiki 架构的页面。
8 月 10 日，Lipton 写了新的，试图将各方讨论的结果以更清晰的方式呈现出来。这篇文章继续成为各方讨论的平台，更多学术上的批评开始浮出水面。更多科学家参与了博客评论以及 wiki 页面的编辑。同日，Deolalikar 在自己的网站上撤下了论文初稿的链接，稍后放上了新一稿。
8 月 11 日，Lipton 了 Deolalikar 对一部分学术质疑的答复。Vinay Deolalikar 贴出了论文的第三稿。
同一日，在学术讨论之外，各方对事态发展的速度和形式本身开始进行反思。Lipton 和陶哲轩等人认为一个借助互联网平台被良好组织起来的讨论可以产生很好的效果，无论对于 Deolalikar 改进他的证明还是对于推进人们关于 P/NP 问题本身的了解都有益处。而另一些科学家，以 Impagliazzo 为代表，认为网络讨论导致了人们反应过度，浪费了太多本可以从事其它研究的时间。这一论点引起了大量争论。
8 月 12 日，Lipton 了一封来自 Neil Immerman 的信，指出了两个此前未被认真讨论的漏洞。
8 月 13 日，Deolalikar 贴出了一篇关于自己的证明的解释性文档。
8 月 14 日，在很多科学家的共同讨论中，人们逐渐厘清 Deolalikar 的论文的根本问题在于把两个没有在论文中被严格定义出来的直观概念混淆在一起，从而做出了不完善的论证。
8 月 15 日，Lipton 贴出了他对于一周以来讨论的总结。人们关于论文的看法——即证明不能成立——已经趋于稳定（当然这不能排除大家都同时犯了错误的可能性），随后的发言越来越多地集中于更抽象的层面，并且至今仍在继续。什么是P问题？NP问题？NPC问题？三者关系如何？_百度知道
什么是P问题？NP问题？NPC问题？三者关系如何？
提问者采纳
给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）;P事实上很直观,这些问题可以用一个确定性算法在多项式时间内判定或解出，比如找出无向图中的哈米尔顿回路问题.2，你能说他很难解么1;NP。比如前面说的哈米尔顿回路问题就是一个NPC问题、NP完全问题此外请注意，我们可以在多项式时间内判断这个答案是否正确;&gt。比如说对于哈米尔顿回路问题;路径问题，最小边覆盖问题（注意和路径覆盖的区别）？刚才说了，简单的数组排序问题是P类问题。NPC问题的历史并不久，但是P属于NP，只不过现在还无法证明，所以也是NP问题。所以，我们一般认为NPC问题是难解的问题?这个问题至今还未解决，所以都是难解的问题，比如.NPC问题存在着一个令人惊讶的性质。类似哈米尔顿回路&#47. 3,而只是要求给出一个确定性算法在多项式时间内验证它的解;&gt，P是否等于NP，cook在1971年找到了第一个NPC问题，C代表complete）.比如说排序，但是我们发现如果给了我们该问题的一个答案，则所有的NP问题都可以在多项式时间内求解，现在还不知道是否有P=NP或者P&lt,找最短路径等。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题，但是后来人们发现还有一系列的特殊NP问题。NP这个类事实上也很有趣,它并不要求给出一个算法来求解问题本身，货郎担问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能），即如果一个NPC问题存在多项式时间的算法，等等很多问题都是NPC问题,我们通常在编程中求解的问题大多都是P类问题，此后人们又陆续发现很多NPC问题，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题，这类问题的特殊性质使得很多人相信P&lt，所有的P类问题都是属于NP问题的、NP问题然而有些问题很难找到多项式时间的算法（或许根本不存在），NP问题不一定都是难解的问题，集团问题！。NP完全问题是求NP中判定问题的一个子类！这是因为，现在可能已经有3000多个了。这类特殊的NP问题就是NP完全问题（NPC问题。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，但是现在的问题是，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。NP是一个判定问题类，即P=NP成立。P类问题就是所有复杂度为多项式时间的问题的集合;NP。显然,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解、P问题P是一个判定问题类
提问者评价
原来是这样，感谢！
来自团队：
其他类似问题
为您推荐：
其他1条回答
多个人一起……NPCP：personNP：游戏里的就上面来看
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁