|
2010年8月6日，惠普实验室的科学家Vinay Deolalikar 宣称，他证明了计算机科学中长期悬而未决的重要问题P!=NP。虽然验证一个证明的完整性和有效性，需要一个漫长而严谨的过程，但这个尝试仍然值得我们为之兴奋。 以下是相关网址： 1, Vinay Deolalikar 官方主页 http://www.hpl.hp.com/personal/Vinay_Deolalikar/ 2, 证明草稿的全文 http:///p-vs-np-12pt.pdf 3, Greg and Kat的博客http:///blog/2010/08/07/p-n-np/ 4, Cook(大牛人)的博客http://rjlipton./2010/08/08/a-proof-that-p-is-not-equal-to-np/ 5, Ryan McElroy的博客http://arcanius./blog/n-np-problem-solved 6, 维基百科 http://en./wiki/P_versus_NP_problem P!=NP得证意味着什么呢？P!=NP如果得证，一个直接结果是为解决NP完全问题（许多类型各异的抽象的逻辑问题其实都是识别悖论的问题，这类问题统称NP完全问题）提供了重要依据，NP完全问题的重要性在于，表面上看起来这些问题各不相关（走迷宫、解密码、魔方及填字游戏这些问题都可以概括为NP完全问题,目前已知的NP完全问题有3000余个），但这些形态各异的问题都包含相同的内核（即都是等价的）。面对整个NP完全问题家族，只要找到了一个通解，则意味着人类的众多经典逻辑谜题和智力题得到了“一揽子”解决。 |
|
|
