Sent to you by tony via Google Reader:
P vs NP是克莱研究所的千禧年难题大奖中宣布的7道数学世纪难题中的一道。这7道难题分布在数学的不同分支，任一道难题的解决都被认为会对相应的分支有重大的影响。P vs NP问题属于理论计算机这个数学分支。 目前为止，这七道难题中唯一被确认证明的是庞加莱猜想，2006年由俄罗斯数学家格里戈里·佩雷尔曼证明。如果Vinay Deolalikar的证明正确，他将很有可能成为第一位领取千禧年难题百万大奖的人（佩雷尔曼拒绝了百万奖金）。
P vs NP问题，简单地说，就是是否每一个容易验证正确性的问题都能很"快"地计算出来？比如说，要验证一个整数是否整除另一个整数是很"快"的，那么给出一个整数，是否能很"快"找出它的一个因子？这里的"快"在理论计算机中有严格的定义，就是所需时间小于一个关于输入长度的多项式，我们也说这个算法可以在多项式时间内解决这个问题。这里牵涉的是算法的时间复杂度，"快"不是绝对意义上的，只是从级数上（主要是和指数级）的比较。
P的正式称呼是"确定性图灵机多项式时间复杂度"，而NP则是"非确定性图灵机多项式时间复杂度"。在理论计算机中，"判定问题"是这样的一类问题，对于某个输入，我们只需要输出"是"或者"否"作为答案。P和NP都是判定问题所组成的集合。如果对于一个判定问题，存在一个能在多项式时间解决它的算法，那么这个判定问题就在P中。如果对一个判定问题，存在一个算法，对于一个肯定的输入，都有一个"旁证"，而算法可以在多项式时间内利用旁证对这个输入进行正确的肯定判定，那么这个判定问题就在NP中。
P vs NP问题，问的正是P是否等同于NP。我们知道，NP包含P，但是在NP中有一类叫NP-完全的问题，至今都没有算法可以容易地解决它们。如果这些问题中有一个属于P的话，NP就等于P；否则，NP就不等于P。P vs NP问题在理论计算机中占有重要的地位，虽然至今为止还没有人确切证明出P是否等于NP，但是主流的推测是P不等于NP，很多应用算法就是基于这样的假设，而许多加密算法的保密性也是建立在P!=NP的前提上的，比如说著名的RSA。P vs NP问题的解决无论对于理论还是实践都有很大的影响。
Vinay Deolalikar的证明横跨了统计、逻辑、统计物理、计算复杂度等学科。他从一个NP-完全问题——可满足性问题（SAT）——入手，尝试证明没有算法可以容易地解决这个判定问题。他先将问题的解的统计特性与一个逻辑模型联系起来，再利用逻辑模型得到一个对算法计算时间的限制。然后他用统计物理的工具，得到了对一类输入——随机kSAT输入——的解的统计特性，将这个统计特性注入此前的逻辑模型中，他证明了对随机kSAT输入，没有算法在多项式时间内解决可满足性问题，从而证明P不等于NP。
现在仍不能确定Vinay Deolalikar的证明是否正确。他已将证明用电子邮件发到数位不同领域的专家手上审核。在惠普实验室他的个人页面上，他发表了一个声明，澄清在网上泄露的证明只是初稿，专家的审核尚未完毕，一个最终的版本会在近期内发布。
尽管P vs NP相当困难，此前也有不少人对它进行过失败的尝试，但对于这个来自这个领域研究人员的证明还是有希望的，让我们拭目以待。
消息来源：原创
作者：fwjmath
本文地址（转载请注明出处）： 复制
收藏、分享这篇文章： 
Things you can do from here:
- Subscribe to 科学松鼠会 using Google Reader
- Get started using Google Reader to easily keep up with all your favorite sites
No comments:
Post a Comment