【理论计算机科学核心问题】P ≠ NP 已经得到证明？
惠普研究实验室的研究员Vinay Deolalikar声称证明了P≠NP。 P/NP问题涉及的是复杂度类P与NP的关系，P事实上是NP的一个子集，NP是指非确定性图灵机在多项式时间内计算的问题，而P是指确定型图灵机在多项式时间内解决的问题。P是否等于NP是克雷数学研究所的千禧年大奖难题之一。Deolalikar的论文长达100页，目前尚未经过同行审议，因此任何人都可以在论文中寻找漏洞或错误。如果Deolalikar的证明是正确的，那么他将有资格获得克雷提供的百万美元奖金。
下面附上Deolalikar的邮件内容： （上述消息来自：http://news.cnblogs.com/n/70334/）
Dear Fellow Researchers,
亲爱的研究伙伴们：
I am pleased to announce a proof that P is not equal to NP,which is attached in 10pt and 12pt fonts.
我很高兴宣布一个P不等于NP的证明（在附件里，有10号字和12号字两种版本）。
The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.
证明需要把数学里多个领域的一些原理联系起来。构建此证明努力的方向主要在于发现不同领域间概念联系的一条链，并通过统一的视角来看待它们。其次在于证明力每个阶段所面临的一些技术障碍。
This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.
这项工作构建在许多有名望的研究者在各自领域里做出的重要成果之上。讲述这篇论文的时候，我的意愿是给读者提供这个证明总体架构的一些想法。各个章节里技术和计算的细节被尽可能地压缩了。
This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.
这项工作是本人以惠普实验室研究员身份独立进行的，其他人亦不知情。在过去两年里，开始做这个证明之前，我有若干次尝试过其他想法组合，但没有成功。
Comments and suggestions for improvements to the paper are highly welcomed.
非常欢迎各位提出意见和改进的建议。
（中文翻译来自rhapsody ^^~）
【P与NP问题简介】
P = NP?
这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。它是克雷研究所的七个百万美元大奖问题之一，在2006国际数学家大会上，它是某个1小时讲座的主题。
要说起P和NP是什么东西，得先从算法的多项式时间复杂度谈起，注意，这里面的两个P都是指Polynomial（多项式）。
一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模就是n。注意，在某些时候，输入规模是要值得注意的，比如判定一个数n是否是一个质数这个问题，它的输入规模并不是n，而是log(n)，因为一个数n用大约log(n)位就能表示出来了，这也是为何枚举因子判定素数的算法并不是多项式时间算法的原因。
如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。注意：这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法，与计算模型的具体的物理实现没有关系，虽然大多数假想的计算模型不可能有任何物理的实现。
P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问题集合，这里N是Non-Deterministic（非确定）的意思。
脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定问题（判定问题指只需要回答是和不是的问题），而NP问题则是指那些其肯定解能够在给定正确信息下在多项式时间内验证的判定问题。比如，要判定一个数是合数，如果给我一个约数，我们就很快判定它就是合数。所以判定一个数是合数的问题属于NP。 下面是一些NP问题的例子：
零子集和问题
给n个整数，判断是否可以从中找到若干个数，其和为0。
旅行商问题
有n个城市，一个推销员要从其中某一个城市出发，不重复地走遍所有的城市，再回到他出发的城市。问这个推销员的最短路程(是否小于指定的K)。
从上面的定义知道，NP包含P。P vs NP问题指P是否完全等于NP，即确定型图灵机和非确定型图灵机的性能是否一样。
人们为何要提出NP问题？因为，大多数遇到的自然的难解问题，最后都发现它们是NP问题。如果我们能证明NP跟P的关系，则解决了无数问题的算法复杂度问题。
NP里面有无数个不同的问题，我们是否要一个一个地判定它们是否属于P呢？P vs NP问题的美妙和简洁之处便在于在NP中，有一个子类，NP完全(NP Complete，简记为NPC)问题，指的是那些NP中最难的那些问题：所有其它的NP问题都可以归约到这些NP完全问题。也就是说，只要这些NP完全问题的某一个得到解决，无论是证明其存在多项式算法，还是不存在，都意味着P vs NP问题的解决。
而几乎所有NP里面无法确定是否属于P的问题最后都被证明为NP完全。正因为如此，多数理论计算机学家都猜测P≠NP。目前已知的NP完全问题数以千计，上面引用中的例子都是完全问题。
一个很自然的想法是如果NP≠P，则NP-P里面的问题都是完全问题。至少有两个自然的问题，一个是大数分解（给出一个数的质因数分解式），另一个是图同构问题（给出两个图，它们是否同构），它们既没有被证明是P的，也没有被证明是NP-完全。但是更惊人的是还有这个定理：
如果NP≠P，那么NP-P中存在非NP完全问题。
当然，这种问题具体是什么样子，是无法用直观的语言表示出来，它纯粹是一个数学上的构造性证明。
历史上的进展
从上个世界70年代初这个问题被Cook提出以来，人们发展了各种工具来试图解决它，下面引自堵丁柱与葛可一的《计算复杂性导论》前言：
人们在七十年代开始对NP-完全问题的研究主要是横向发展，也就是以许多不同的计算模型来分析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型的研究一方面使我们对难解问题有了更深一层的认识，一方面也产生了一些预想不到的应用。最显著的一个例子就是计算密码学的革命性突破：基于NP问题的公钥密码体系。另一个有名的例子是线性规划的多项式时间解的发现。
到了八十年代中，对NP-完全问题的研究有了纵向的突破，在许多表面看来并不相关的计算模型之间发现了深刻的刻划关系。这些刻划关系不但解决了几个令人困扰多年的未解问题，同时也刺激了其它相关领域的发展。其中之一是对线路复杂性的研究发现了一些问题在某种有限制的线路模型中必有指数下界。这些结果使用了组合数学与概率方法等新的数学工具，并且解决了一个有名的有关多项式分层的未解问题。另一个更重大的结果是以概率可验证明对NP类的刻划。由此得出了许多组合优化问题近似解的NP-完全性，从而刺激了算法界对近似算法研究的新热潮。这个结果来自于对交互证明系统这个概念的扩展，并且使用了线性代数与编码理论等数学证明技巧。
但是，明显的，目前还没有一个看上去有希望的方向。相反的，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P vs NP问题。这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。
（上述简介来自：http://zhiqiang.org/blog/science ... of-the-problem.html）
【附件：证明的论文】
下边就是Vinay Deolalikar那个长达100页的证明，论文名字就叫“P ≠ NP”，有兴趣的回复可见附件^^~：
**** Hidden Message ***** 有兴趣
虽然看不太明白 对此表示怀疑 难道是又一个哥德尔定理？ 人工智能中的NP难问题？ 我连标题都看不懂 “横”好，真希望这证明是正确的。
页:
[1]