求真分享 http://blog.sciencenet.cn/u/zlyang 求真务实

博文

[请教]“P vs NP Problem”为什么这么困难?

已有 9314 次阅读 2010-8-13 19:55 |个人分类:科研|系统分类:科研笔记| Mathematics, institute, clay

[请教]“P vs NP Problem”为什么这么困难?

 

P vs NP Problem
http://www.claymath.org/millennium/P_vs_NP/

“P vs NP”近来又开始火热起来。 
该问题看上去不困难,甚至一眼就知道结果“P≠NP”。
可是为什么还需要证明?
并且证明这么困难?
  

    非确定型图灵机 Non-deterministic Turing machine
的“最”严格学术定义是什么?
 

真理”、“真理客观性”与“证明
之间是什么关系?
 

   谢谢您的指点!

 

“社会承认的证明”才是证明。(Yuri Manin)
A proof only becomes a proof after the social act of “accepting it as a proof”.
http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/

真得很有趣。

 

相关链接

[1]《“P对NP(P versus NP, P vs NP)”问题的描述、难度、可能的答案》
http://bbs.sciencenet.cn/forum.php?mod=viewthread&tid=266338

[2] Gerhard J Woeginger: The P-versus-NP page
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

[3] 杜立智《印度人P!=NP证明的最新进展》
http://www.sciencenet.cn/m/user_content.aspx?id=352633

[4] 潘纲《“P!=NP”:这次真得被证明了吗?【最新进展!】》
http://www.sciencenet.cn/blog/user_content.aspx?id=351664

[5]《Vinay Deolalikar宣称自己证明了“P!= NP”(P 不等于 NP)》
http://bbs.sciencenet.cn/showtopic-106360.aspx

  

 

————————  补充附录 ————————

P vs. NP,我们从过去的一周中学到了什么?

http://apple4.us/2010/08/p-vs-np-what-do-we-learn-from-the-past-week.html

这篇文章的标题是模仿 Suresh Venkatasubramanian 的一篇博客文章。他是犹他大学的一名计算机系助理教授。在过去的一周里,他在自己的博客上连续发表了好几篇文章,讨论 Vinay Deolalikar 在 8 月 6 号公布在网络上,后来又几经修改的那篇备受争议的宣称证明了 P ≠ NP 的论文。

他不是唯一一个这样做的科学家。在过去的一周里,以博客为平台参与到关于这篇论文的大讨论的,还包括(并且远远不限于)下面这些名字:Richard Lipton,Timothy Gowers,Neil Immerman,Russel Impagliazzo,Harvey Friedman,以及陶哲轩。这些人全部都是世界级的顶尖科学家,通常情况下,即使在国际学术会议上也未必能够看到他们同时出现。而这一次他们以博客(主要是 Lipton 的博客和评论)和 wiki 为平台,展开了比通常在学术会议上更为激烈的讨论乃至辩论。其主题涵盖了从 Deolalikar 证明的有效性,到对 P/NP 问题更为一般的分析,乃至抽象的学术方法论等等各个层面。这讨论直至今日为止,仍在进行。上千条发言大多洋洋洒洒,众人讨论态度之谦冲和平,内容之深入细致,足堪为网络时代的一个完美的表率。阅读这些讨论是令人深受教益的过程,无论是在学术上还是在更抽象的层面上都是如此。

随着整个故事的尘埃渐渐落定,现在已经可以回头看看,在过去这脚步匆促的一周里围绕着 Deolalikar 的这篇论文发生了哪些事情。下面提到的人物均为学术界内的重要科学家,其身份不一一注明。

  • 8 月 6 日,Deolalikar 在网络上张贴了自己的论文初稿。
  • 8 月 8 日,Lipton 在博客上讨论了这篇论文,给出了略显乐观的评价:这是一个值得认真对待的证明。这篇文章引来大量严肃的学术性回复,大多来自业内人士,各方看法不一。
  • 8 月 9 日,Lipton 在参考各方反应的基础上同 Ken Regan 合写了一篇新的博客文章,指出了 Deolalikar 证明思路中的一些重大漏洞,对它的整体评价口吻较前日明显低调了许多。
  • 同日,因为 Lipton 博客文章后面大量有价值的评论值得梳理,Venkatasubramanian 建立了一个可以被公众编辑的 Google Docs 文档以整理这些讨论。翌日,在陶哲轩的帮助下,该文档被转换成一个 wiki 架构的页面
  • 8 月 10 日,Lipton 写了新的博客文章,试图将各方讨论的结果以更清晰的方式呈现出来。这篇文章继续成为各方讨论的平台,更多学术上的批评开始浮出水面。更多科学家参与了博客评论以及 wiki 页面的编辑。同日,Deolalikar 在自己的网站上撤下了论文初稿的链接,稍后放上了新一稿。
  • 8 月 11 日,Lipton 贴出了 Deolalikar 对一部分学术质疑的答复。Vinay Deolalikar 贴出了论文的第三稿。
  • 同一日,在学术讨论之外,各方对事态发展的速度和形式本身开始进行反思。Lipton 和陶哲轩等人认为一个借助互联网平台被良好组织起来的讨论可以产生很好的效果,无论对于 Deolalikar 改进他的证明还是对于推进人们关于 P/NP 问题本身的了解都有益处。而另一些科学家,以 Impagliazzo 为代表,认为网络讨论导致了人们反应过度,浪费了太多本可以从事其它研究的时间。这一论点引起了大量争论。
  • 8 月 12 日,Lipton 贴出了一封来自 Neil Immerman 的信,指出了两个此前未被认真讨论的漏洞。
  • 8 月 13 日,Deolalikar 贴出了一篇关于自己的证明的解释性文档。
  • 8 月 14 日,在很多科学家的共同讨论中,人们逐渐厘清 Deolalikar 的论文的根本问题在于把两个没有在论文中被严格定义出来的直观概念混淆在一起,从而做出了不完善的论证。
  • 8 月 15 日,Lipton 贴出了他对于一周以来讨论的总结。人们关于论文的看法——即证明不能成立——已经趋于稳定(当然这不能排除大家都同时犯了错误的可能性),随后的发言越来越多地集中于更抽象的层面,并且至今仍在继续。

这是极为罕见的一幕。也许甚至可以说,这是有史以来科学界从未发生过的一幕。仅仅十年前,科学家之间的通信和面对面的交谈还几乎是科学交流仅有的方式。虽然人们一般会用「日新月异」形容科技发展的速度,但是科学研究方式本身的变迁则要缓慢许多。而这一点似乎一夜之间就改变了。

一个自然而然浮现出的问题是,在后 web 2.0 时代,传统的论文匿名评审制度会面临怎样的挑战?Deolalikar 声称他仍然会把自己的论文按照传统的方式投递给学术刊物,可是任何一个学术刊物的评审显然都不可能无视在网络上业已出现的讨论。这些讨论对传统的评审机制是一种补充,还是一种颠覆?正如 Friedman 在评论中所指出的,在未来,也许网络会替代学术期刊成为人们发表学术成果的主要方式,而基于网络互动的评审机制会被建立起来。这会很快成为现实么?

在更高的层面上,这个案例还生动地展示出,一个社会化的网络会在多大程度上改变人们的工作——而非仅仅是社交或者游戏——方式,以及这种改变是多么具有争议性。下面的争论也许可以很好反映出人们的分歧。它始自 Impagliazzo 的一则评论

像陶哲轩和 Gowers 这样的人在这几天功夫里本来可以做很多事的,所以如果(这篇论文被发现)此路不通,那这几天浪费得实在是有点可耻。

陶哲轩本人温和地反驳了这一批评:

我想这段时间以来,我们在一起专注于这个讨论,这比每个人都听说这个消息然后所有的专家们都各自花时间读整篇文章要有效率一些。这个办法实际上降低了总时间消耗,尽管它的消耗是在明处。

这一争论很像是人们习以为常的关于社会化网络的批评在一个特殊场合下的翻版:对它的批评集中于它浪费参与者的时间,分散人们的注意力,使他们不能更有效率地做本职工作。而它的辩护者则认为它促进了信息的交换,提高了人们思考和分析问题的效率,等等。

但是更进一步,基于博客和 wiki 的社会化网络能不能做到更多呢?陶哲轩在另一则评论里不无担忧地说:

如果这些讨论的全部意义仅仅在于审阅这篇论文,那我实际上很同意 Impagliazzo (关于浪费时间)的观点。我其实觉得,既然我们都在这里,我们有机会做更多的事情,不仅仅是审阅而已。

他的担忧在某种意义上被证实了:在过去的一周时间的热烈而深入的讨论中,人们以史无前例的速度分析并否定了这篇冗长(100 页)而专业的论文,但是也仅此而已。很多人从中学到了不少东西,对很多问题的理解更为深刻,但是并没有任何新的成就诞生出来。(如果有的话,这个故事会显得戏剧性许多。)

这正是从 Twitter 到 Facebook 再到 Quora 等等的网络平台都在面临着的问题。借助它们,人们可以更好的交流信息,但是如何在社会化的基础上更好地创造出新的知识呢?工业化的历史已经证明,一群人可以创造出超出它的所有成员能力范围之外的物质成果。但是在精神文明的领域里,事情似乎远不是这么简单。

David Dill 在 1999 年曾经说过:Don’t rely on social processes for verification (社会化的审查过程是靠不住的)。在过去的一周里,人们看到了这句话在某种意义上的一个反例。如果把这句话中的 verification 换成 creation 呢?这有点像是一个我们这个时代的,关于巴别塔的问题。



https://blog.sciencenet.cn/blog-107667-352731.html

上一篇:躺在淤泥中的荷花
下一篇:英国小莫奈 Kieron Williamson
收藏 IP: 202.113.12.*| 热度|

3 邹晓辉 何学锋 crossludo

发表评论 评论 (6 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-11-13 14:46

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部