4月
07
2013

P/NP问题——未来数学家挑战

复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题;类NP由所有可以在多项式时间内验证解是否正确的决定问题组成,或者等效的说,那些解可以在非确定型图灵机上在多项式时间内找出的问题的集合。很可能,计算理论最大的未解决问题就是关于这两类的关系的:

PNP相等吗?

在2002年对于100研究者的调查,61人相信答案是否定的,9个相信答案是肯定的,22个不确定,而8个相信该问题可能和现在所接受的公理独立,所以不可能证明或证否。对于正确的解答,有一个$1,000,000美元的奖励。

NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用,它们可以大致的被描述为那些在NP中最不像在P中的(确切定义细节请参看NP-完全理论)。计算机科学家现在相信P, NP,和NPC类之间的关系如图中所示,其中PNPC类不交。

假设PNP的复杂度类的图解。如P =NP则三个类相同。

简单来说,P = NP问题问道:如果是/不是问题的正面答案可以很快验证,其答案是否也可以很快计算?这里有一个给你找点这个问题的感觉的例子。给定一个大数Y,我们可以问Y是否是复合数。例如,我们可能问53308290611是否有非平凡的因子。答案是肯定的,虽然手工找出一个因子很麻烦。从另一个方面讲,如果有人声称答案是"对,因为224737可以整除53308290611",则我们可以很快用一个除法来验证。验证一个数是除数比找出一个明显除数来简单得多。用于验证一个正面答案所需的信息也称为证明。所以我们的结论是,给定正确的证明,问题的正面答案可以很快地(也就是,在多项式时间内)验证,而这就是这个问题属于NP的原因。虽然这个特定的问题,最近被证明为也在P类中(参看下面的关于"质数在P中"的参考),这一点也不明显,而且有很多类似的问题相信不属于类P

像上面这样,把问题限制到“是/不是”问题并没有改变原问题(即没有降低难度);即使我们允许更复杂的答案,最后的问题(是否FP = FNP)是等价的。

http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html

本文作者:
本文链接:http://fengg.net/blog/archives/548

By Feng in: 数学算法 | 标签: | (1,304)
欢迎订阅: 订阅到iGoogle或Google Reader 订阅到鲜果 订阅到抓虾 订阅到我的雅虎 订阅到网易有道 订阅到QQ邮箱
收藏分享: Google书签 | QQ书签 | Del.icio.us | Technorati
There are no comment,Leave a comment»

RSS feed for comments on this post. TrackBack URL


Leave a Reply

可以使用部分XHTML标签:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Feng(Sitemap) Powered by WordPress. Host by 理想空间. Admin. (TOP)