P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领域的最大难题，关系到计算机完成一项任务的速度到底有多快。
P对NP问题是Steve Cook于1971年首次提出。“P/NP问题”，这里的P指多项式时间（Polynomial），一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算；NP指非确定性多项式时间（nondeterministic polynomial），一个复杂问题不能确定在多项式时间内解决，假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P=NP。比NP问题更难的则是NP完全和NP-hard，如围棋便是一个NP-hard问题。2010年8月7日，来自惠普实验室的科学家Vinay Deolalikar声称已经解决了“P/NP问题” ，并公开了证明文件。
注：以上内容全部援引自百度百科。侵删。
P对NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领域的最大难题，关系到计算机完成一项任...
目录 时间复杂度与多项式时间 确定性算法与非确定性算法 判定性问题 规约/约化 P问题 NP问题 NPC问题 P=...
今天看了后，终于能大致理解，P问题，NP问题之间的简单区别。 P问题---多项式可解决的问题； NP问题----给...
来源：maxtrix67：http://www.matrix67.com/blog/archives/105 P问...
P问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题 NP问题：NP问题不是非...
参考链接：什么是P问题、NP问题和NPC问题 时间复杂度 此处我们分为两类，多项式级的复杂度和非多项式级的复杂...
这是困扰计算机系的同学们50年的经典问题：P是否等于NP? P就是能在多项式时间内解决的问题，NP就是能够在多项式...
左图在假设P≠NP的情况下有效，右图在假设P=NP的情况下有效 在假定P≠NP的情况下, 有 NP问题：可以在多项...
P类问题：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。 NP问题：是指可以在...
NP完全性 P类问题：P类问题就是在多项式时间内可以解决的问题。NP类问题：NP类问题是指那些在多项式时间内可以被...
本文标题：p对np问题
本文链接：https://www.haomeiwen.com/subject/ixwpwrtx.html
网友评论