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问题” ,并公开了证明文件。
注:以上内容全部援引自百度百科。侵删。
网友评论