期待大神的出现,NP完全问题
日前,HP科学家Vinay Deolalikar宣称其已经证明了P!=NP,目前正在接受其他计算机理论科学家的确认。
我彻底无语了,如果他的证明是真实的话,他的意义不仅仅是解决了人类数学史上七大难题中最难的一道。诺贝尔数学奖,图灵奖更不在话下,更主要的是,从理论基础上解决了很多计算机学科无法盖棺定论的问题。
鄙人有幸得到论文全文,无奈洋文不行,修行不深,粗读一遍,不知所云。
首先,我们来了解几个常识性的问题。
1.数学七大难题
美国麻省Clay数学研究所悬赏100万美元用于解决人类历史上的七大数学难题
P问题与NP问题
Hodge猜想
Poincare猜想
Riemann假设
Yang-Mills存在性和质量缺口
Navier-Stokes方程的存在性与光滑性
Birch和Swinnerton-Dyer猜想。
2.什么是P问题,NP问题
P问题,通俗地讲一个问题可以找到一个可以在多项式的时间内可以解决的算法的问题。
NP问题,是指可以在多项式时间内验证一个解的问题。
这些都属于理论计算机科学的问题,理解起来很麻烦,证明起来就更麻烦了。
好了,理解了这几个常识,我们就来分析一下,为什么要解决P问题和NP问题关系的问题(好绕啊)。
我举一个最通俗的例子。
对于一个加密算法,我们有一个输入,一个输出,一个映射关系,这其中一般情况下是一个输入对应一个或多个输出的问题(我说的是一般情况下)。
那么,我们在多项式时间内根据输入和输出找到映射关系就属于P问题。
而我们能够在多项式时间内根据输出得到一个输入,属于一个NP问题。
好了,P问题是否等于NP问题的意义就在于,如果我能够在多项式时间内根据一个密文得到明文,那么是否意味着我可以在多项式时间内找到加密算法。
如果这个问题可以成立,那就可以推出,我们今天大部分的加密算法(因为今天我们的大部分算法可以证明是NP问题),是在多项式时间内可以找到加密算法的,这是一件很恐怖的事情。
不过庆幸的是,我们目前的大部分的猜测都是P不等于NP。
而且我们目前很多理论的推测都是基于P不等于NP的前提的。
为什么,我们会认为P不等于NP呢?
这里我们要引入另一个概念,NPC问题,也称作NP完全问题。
为了说明NPC问题,我们引入一个新的概念“约化”。
一个问题A可以约化成问题B的含义是:可以用问题B的解法来解答问题A。
问题A可以约化成问题B的一个直观的条件就是问题B的时间复杂度高于等于问题A
约化的准确的概念,应该是问题A的输入经过一定的规则处理可以转化成问题B的输入,并得到正确的结果。
至此,我们可以给我NPC问题的概念:1.他是一个NP问题。2.所以的NP问题都可以约化成他。
而找到一个NPC问题的条件是:
那么我们我谈谈P问题和NP问题的关系。
既然我们认为所有的NP问题都可以约化成NPC问题,那么我们就可以把问题简化成寻找NPC问题是否存在一个多项式解答的问题。
如果我们能够找到NPC问题的多项式解答,那么P问题就等于NP问题了。
但是显然,这是不可能的,虽然我们无法证明他是不可能的。
这也就是为什么能证明出这个问题的人会称之曰大神。
呜呼,说得这么多,我自己都快绕糊涂了。。。
如果你发现写得不对的地方,一定要指出来,谢谢。
从即日起,继续膜拜大神的著作。







最近评论