刚刚过去的这个周末，计算机科学界最热门的话题莫过于一位惠普试验室的资深研究员，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，这是个相对而言并不太令人惊讶的，冲击力也不算太强的结论（虽然也很困难）。另一方面，一个理论成果的影响传递到现实世界会经历漫长的过程。
但是无论如何，这条新闻总是个令人兴奋的好消息，特别是和这世界上正在发生的大多数新闻相比较而言，更是如此。
17 Comments so far
Leave a comment
Fields in bold are required. Email addresses are never published or distributed.
Some HTML code is allowed:<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>
URLs must be fully qualified (eg: http://apple4.us),and all tags must be properly closed.
Line breaks and paragraphs are automatically converted.
Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.
作为曾经还努力发稿的一位忠实读者来说，我实在是不想说现在的apple4us到底是什么玩意？既没有apple，也没有us！
同意，最近的文章好奇怪。
Mac和iPhone现在已经普及了，无法装逼了，所以就得写点别的东西啊，比如什么如何创业啊（可笑的是A4U好像没人成功创业过，却特别喜欢教别人如何创业，哦对了马俊仁不用会长跑也能当长跑教练），什么高深到没人懂的数学理论啊，期待在A4U看到更多教人装逼的东西，什么哲学啊，物理啊，人体解剖啊，希伯来语啊全整上啊
不管怎么说，都是个好消息，但是境界太高了～
这个集合论的东东应该是数学家解决的问题吧
@不等于 這是計算理論的問題，不是集合論
出现这种毫无关联的文章 莫名其妙 这里是CNBETA还是松鼠会还是糗事百科
嫌疑人x的献身
计算机科学家从来都没有成功解决过数学问题，他们的想法对数学家来说太不严谨了，这也是为什么他们所写的系统都有大量的bug.
好像很深奥的样子
Apple4us怎么发这种文章了。。。
很喜欢这篇文章，很不和谐的支持一下:)
凡是不和谐的东西，我都喜欢。
话说我看不懂这个，所以还花了点时间了解多一点P/NP……
相信最近很多人都在不懂装懂吧？
apple4.us太牛了！专业就是专业！
3P=NP么。。
最讨厌印度阿三，就是母狗生出来的SB
唯一的建议是首页文章简略显示部分，否则太长，影响阅读兴趣