不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

点评《紐約客》科普“P versus NP”-流行的NP定义

已有 3875 次阅读 2016-8-11 12:00 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| versus

                                         - 科学的每一部门都是对于整个自然界的一种描述,而这种描述通常都是近似性的。事实上,每件我们所知道的事都不外是对真理的一种近似叙述……我们现在学习的态度就是准备随时放弃或更正。《费因曼物理学》  

                                         - 物有本末,事有终始,知所先后,则近道矣。《大学》

《紐約客》科普“P versus NP”,通俗、精简地介绍了这个著名的“千禧年难题”(  《紐約客》科普“P versus NP”(MAY 2, 2013))。此外还有美剧《基本演绎法》(Elementary,又译:现代福尔摩斯)的第2季第2集中也谈及此问题,说两位研究NP问题的数学家被谋杀了,凶手是同行,因为被害者即将证明“P=NP问题”,她为独吞成果而下了毒手。剧中只用了一句话来介绍 P=NP的意义:“能用电脑快速验证一个解的问题,也能够用电脑快速地求出解”。

媒体把“P versus NP”这样高居庙堂的理论问题带入了普通人们的视野,是谓“旧时王谢堂前燕,飞入寻常百姓家”,这正反映了计算机给当代社会所带来的深刻变化和影响。然而,这样的科普,一方面能使外行多少知道这个问题的大概情况,另一方面,可能使很多“内行”更糊涂,因为作者是按现有的理论框架来介绍“P versus NP”的,并没有意识到该问题真正的困难所在。在此意义上,《紐約客》上的文章不仅是大众的好奇,更是专家的困惑,也正是作者所指出的这个问题在诸“千禧年”难题中的特殊性。

我们认为,导致“P versus NP”成为“世纪难题”的根本原因,在于NP的流行定义(多项式时间可验证)导致了NP的本质“不确定性”的消失,从而暗中肯定了“NP=P”,然而就一般的常识而言,人们又直觉:NP ≠ P,如此致“P versus NP”成为悖论,乃至“世纪难题”。所以,“P versus NP”的真正难度并不在答“NP=P?”,而在问“什么是NP?”

现代管理学之父彼得•德鲁克(Peter Drucker)将要离世的时候,做出一个这样的结论:“在管理决策中最常见的错误,是我们强调寻找正确的答案,而不是正确的问题。”他还说:“最严重的错误,不是回答错误,真正危险的事,是问错了问题。”此现象不仅仅表现在管理决策中,更见诸于生活中的方方面面,或许可以说,这是人的认知的最大盲点。

那么,为什么“问题”如此重要?因为“问题”是认知和行为的原点,围绕着“问题”整个思想和行动才得以展开,也就是说,“问题”界定、打造了我们面对的现实,指引着我们行动的方向。就NP而言,最初是相对P提出来的,即欲区别于已知的具有“确定性”本质的P,然而流行的观念却是“多项式时间可验证”的NP(Nondeterministic Polynomial time),但这样的性质是“确定性”的,是有NP的“不确定性”消失,P与NP的混淆。

我们NP理论工作,旨在算法理论层次上,理清相对于P的NP的概念内涵,即理清在“可计算性”意义上的“确定性”与“不确定性”的关系。“不确定性”这个概念的内涵,远远超过了算法理论这个层次,但在算法理论这个层次理清这个概念,无疑是最基本和最严格的工作。当然,这样的工作需大家参与、达成共识,这本身就是一项艰巨的集体性工作。

在此意义上,我们认为,探讨“P versus NP”这个问题的另一种意义,就是对知识界的整个认知的一个提高,由此我们或许可以理解Hemaspaandra在介绍Gasarch于2012年进行的第二次“P versus NP”调查时的悲叹(http://blog.sciencenet.cn/blog-2322490-856768.html):

-我希望在遥远的未来,当人们读到这四篇文章,可以帮助他们了解,在“P versus NP”还没得到解决的黑暗年代里人们的思想状态(I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved。)

附曾经写的三篇点评《紐約客》文的博文:

-点评《紐約客》文-流行的NP定义(1):http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&quickforward=1&id=891584

-点评《紐約客》文-流行的NP定义(2):http://blog.sciencenet.cn/blog-2322490-892261.html

-点评《紐約客》文-流行的NP定义(3):http://blog.sciencenet.cn/blog-2322490-893312.html




https://blog.sciencenet.cn/blog-2322490-995815.html

上一篇:辨析“circle-free”与“halting” - 定性分析与定量分析
下一篇:NP理论(3):层次与中国传统逻辑
收藏 IP: 194.57.109.*| 热度|

2 杨正瓴 强涛

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

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

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

GMT+8, 2024-3-28 20:52

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部