号外！P！=NP ！

earthengine

http://science.slashdot.org/stor ... ed-Proof-That-P--NP

kaile

P和NP分别是什么

earthengine

楼上的，请移步 维基百科

中文：
http://zh.wikipedia.org/zh-cn/P/NP%E9%97%AE%E9%A2%98
英文：
http://en.wikipedia.org/wiki/P_versus_NP_problem

熊猫阿三

The relationship between the complexity classes P (Polynomial time) and NP (Nondeterministic Polynomial time) is an unsolved problem in theoretical computer science, and is considered by many theoretical computer scientists to be the most important problem in the field.[2] The Clay Mathematics Institute, which is dedicated to increasing and disseminating mathematical knowledge, has included it in its list of Millennium Prize Problems; anyone who provides a satisfactory solution to the problem may be entitled to a USD $1,000,000 prize.[3][4]

In essence, the question P = NP? asks: if "yes"-answers to a "yes"-or-"no"-question can be verified "quickly" can the answers themselves also be computed "quickly"? The theoretical notion of "quick" used here is that of an algorithm that runs in polynomial time, which usually but not always corresponds to an algorithm that is fast in practice.

Consider the subset sum problem, an example of a problem which is easy to verify but whose answer is suspected to be theoretically difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} add up to zero", can be quickly verified with three additions. However, finding such a subset in the first place could take more time. The information needed to verify a positive answer is also called a certificate. Given the right certificates, "yes" answers to our problem can be verified in polynomial time, so this problem is in NP.

An answer to the P = NP question would determine whether problems like the subset-sum problem that can be verified in polynomial time can also be solved in polynomial time. If it turned out that P does not equal NP, it would mean that some NP problems are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.

The restriction to yes/no problems is unimportant; when more complicated answers are allowed the extension to function problems becomes FP = FNP, which has been proven to be equivalent to P = NP.[5]

coredump

暂时还不敢相信，这玩意比哥德巴赫猜想还爆炸性，没有确定性结论出来前，还是要等其他科学家的看法，自己看又没有那个功力。不管证明 P=NP还是证明 P!=NP，都意味着很多结论

coredump

FROM:http://www.matrix67.com/blog/archives/2552

在计算机复杂度理论中，P问题指的是能够在多项式的时间里得到解决的问题，NP问题指的是能够在多项式的时间里验证一个解是否正确的问题。虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在首位。科学家们普遍认为P≠NP是有原因的。让我们来看一看，如果哪一天科学家证明了P=NP，寻找一个解和验证一个解变得同样容易，那这个世界将会变得怎样？

    已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；数据库的串行化、多处理器调度等问题也随之解决，大大提高了计算机的性能。同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上失去了意义。
    算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。
    一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。在新的编程语言中，你只需要用代码指明输入数据与输出数据的关系，而无需关心计算输出数据的步骤。只要这种关系是多项式时间内可计算的，编译器将自动找到解法。在新型编程语言的支持下，人们唯一需要考虑的是，如何把实际问题转化成数学模型。


    利用Occam剃刀原理，困扰人类已久的自然语言处理问题将被一举攻破。只要提供足够多的语言文字材料，计算机将很快掌握这门语言，并反过来为语言学提供新的科学体系。考虑这样一个最优化问题：输入一大批语句样本，它们有的符合语法，有的不符合语法；寻找一个最简单的算法，将这些语句输入这个算法时，算法能正确得出它是否符合语法。显然，这个问题本身是NP的（当然前提是该算法是多项式的），因此计算机可以在多项式时间内找到能判定语法正误的最简算法。我们有理由相信，这个算法也就是人类头脑中正在使用的算法，因此它能够适用于所给材料之外的其它语句，并具有自我学习的功能。分词技术、手写识别、语音朗读、语音识别等难题在一瞬间全部攻破。
    很可能计算机给出的自然语言处理算法完全不同于传统语言学的那一套方法，因此传统语言学本身将受到极大的冲击。字、词、句的概念很可能被重新界定，词类、句式的概念有可能被完全颠覆。
    类似地，所有人工智能问题都将得到解决。我们只需要向计算机提交足够多的情境以及与之对应的正常人反应，计算机就可以找出一种能正确生成出这些反应的最简算法，并且由我们的Occam剃刀假设，这种算法能够适用于更广的范围，完全模仿人类的行为。在网络上，再没有任何办法能够把计算机和人区别开来。验证码将变得毫无意义。
    计算机不仅能轻易通过图灵测试，还能精确地模仿某一个特定的人。如果你能把某个人的网络聊天记录全部搜集起来，把这个人和网友们的对话全部递交给计算机，计算机将会很快学会如何模仿这个人。网络的身份鉴定将变得相当困难，很可能不得不借助一些物理方式。
    数学证明可以完全交给计算机来处理。寻找一个反例和验证一个反例变得同样简单，一切错误的猜想都将瞬间被推翻。事实上，寻找一个数学证明和验证一个证明的正确性也变得同样简单，因此一切正确的命题也能够瞬间找到一个最简的证明。困扰人类数个世纪的数学猜想将逐一获解。数学领域内部将掀起一次革命，数学研究真正成为了一门“提出问题的艺术”而不再是“解决问题的艺术”。数理逻辑等底层研究，以及开创数学新分支并将其形式化，将成为数学研究的主流方向。
    类似地，一切具有解释性并可以形式化的科学都可以借助计算机寻求现象的最佳解释方案。物理学、化学、经济学、心理学等学科都将会受到不同程度的影响。
    md5算法不再有效，判定一个串的md5是否等于给定值与寻找一个md5等于给定值的串一样轻松。RSA算法也不再有效，寻找一个质因子和判断整除性也变得一样简单。事实上，发明任何新的密码算法都是徒劳——计算机可以根据一大批明文密文样本推算出生成密文的算法（只要这个算法是多项式的）。现有的密码学体系彻底崩溃。理论上不具有可预测性的一次一密协议成为唯一安全的密码协议。但人们很快注意到，密码本本身的生成也不能依赖于任何伪随机数算法，必须完全借助于物理算法。从这个角度来说，纯机器的密码协议将不复存在，任何身份验证手续都必须借助物理手段。互联网可能会变得非常不可靠。

本人对复杂度理论涉猎不深，并且叙述颇有些夸大其辞，欢迎网友们探讨、指正、争论和补充。
本文部分参考一篇牛文，已上传至我的空间，强烈建议大家膜拜：http://www.matrix67.com/data/average.ps

key

原帖由 coredump 于 10-8-2010 10:03 发表

                               
登录/注册后可看大图

利用Occam剃刀原理，困扰人类已久的自然语言处理问题将被一举攻破。只要提供足够多的语言文字材料，计算机将很快掌握这门语言，并反过来为语言学提供新的科学体系。

别的不说，自然语言在青山同学的努力下，估计很快有突破性进展。

klux

原帖由 key 于 10-8-2010 10:36 发表

                               
登录/注册后可看大图

别的不说，自然语言在青山同学的努力下，估计很快有突破性进展。

有道理

老蒋

不是吧，真的假的？

如果是真的，这绝对是爆炸性的新闻啊！！

coredump

原帖由 key 于 10-8-2010 10:36 发表

                               
登录/注册后可看大图

别的不说，自然语言在青山同学的努力下，估计很快有突破性进展。

他不是一个人[size=13.8889px]

老蒋

＂The 100-page paper has apparently not been peer-reviewed yet＂

看来还要等牛人来review

不过如果真的证明了 P != NP，虽然是里程碑式的证明，但却其实是个 sad news

如果能证明 P = NP，那是真的能改变世界的轨迹！！ 哎，只是想想罢了～

coredump

FROM:http://apple4.us/2010/08/a-proof-that-p-is-not-equal-to-np.html
P 不等于 NP……么？
by 木遥

                               
登录/注册后可看大图

刚刚过去的这个周末，计算机科学界最热门的话题莫过于一位惠普试验室的资深研究员，Vinay Deolalikar，宣称自己证明了 P ≠ NP。
他的证明目前只有初稿，本来只在私下里流传。但是有人把它捅到了 Slashdot 那里，于是媒体闻风而动。一夜之间，似乎人人都开始讨论这则新闻了。
大家这么激动的原因是这个问题实在太过于重要。它既是数学上的顶尖难题（著名的七个百万美元悬赏的千年数学难题之首），也是计算机科学的基础性问题。并且和许多别的著名数学难题（例如黎曼猜想或者庞加莱猜想）不同，它对于整个信息产业（从而也对于当今世界的方方面面）具有重要的现实意义。
简单的说，在这里 P 指的是「能够很快被解出的问题的集合」（这里「很快」的严格定义是所谓多项式时间内），NP 指的是「能够很快判定一个解是否正确的问题的集合」。P/NP 问题一般表述为 P 是否等于 NP，即「是不是一个问题只要能够很快判定一个解是否正确，它就能很快被解出」。关于这个问题的更详尽的解释，可以参看这篇文章。
人们目前并没有充分证据证明 P = NP 或者 P ≠ NP 两者中任何一个结论，但是大多数人相信 P ≠ NP。如果 P = NP，整个计算机科学和信息技术都会迎来极为重大的变革。关于 P = NP 的现实后果，可以参阅这篇笔调略显夸张的文章。2002 年对该领域专家的一次调查显示，相信 P = NP 以及 P ≠ NP 的专家的比例是 9:61。
以上即为这则新闻的背景。毫无疑问，人们离断言该问题已被解决还有极为遥远的距离。众所周知，任何一个著名且重要的难题都会吸引无数人的关注，各种所谓的证明汗牛充栋，其中 99% 都来自没有受过专业训练的外行，没有任何实际意义。当然这则新闻的主人公并不在此列，他是该领域内一位声名卓著的专家，曾经在这一方向作出过很多重要研究。但是即便如此，他的证明仍然需要经过严格的审查，很可能它很快就被挑出一个细微然而重要的错误，然后迅速被人遗忘。这样的故事发生过很多次，以至于专业人士大多对此新闻持以审慎的态度。
佐治亚理工大学的计算机科学家，美国工程院院士 Richard Lipton 在他自己的 blog 里讨论了这篇论文。简而言之，他认为这是个严肃的，值得认真研究的证明，但是对其中一些证明思路颇为疑虑。在接下来的一段时间里，他和很多该领域的专家一样会开始严格审阅这篇论文的细节。
即使小概率事件真的发生了，这篇论文最后被证明是正确的，我们的生活会有立竿见影的变化么？答案是不会。一方面，他证明的是 P ≠ NP 而非 P = NP，这是个相对而言并不太令人惊讶的，冲击力也不算太强的结论（虽然也很困难）。另一方面，一个理论成果的影响传递到现实世界会经历漫长的过程。
但是无论如何，这条新闻总是个令人兴奋的好消息，特别是和这世界上正在发生的大多数新闻相比较而言，更是如此。

dover

感觉能专心做这种研究的人都很NB，因为成功的可能性太小。

coredump

一经发现很多问题了：Issues In The Proof That P≠NP http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/

不过我看不懂，有没有能看懂的来给大家讲讲？