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

博文

点评《紐約客》文-流行的NP定义(3)

已有 3054 次阅读 2015-5-26 20:39 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| versus

“The most serious mistakes are not being made as a result of wrong answers. The true dangerous thing is asking the wrong question.”

― Peter Drucker

现代管理学之父彼得•德鲁克(Peter Drucker)将要离世的时候,做出一个这样的结论:“在管理决策中最常见的错误,是我们强调寻找正确的答案,而不是正确的问题。”他还说:“最严重的错误,不是回答错误,真正危险的事,是问错了问题。”

此现象不仅仅表现在管理决策中,更见诸于生活中的方方面面,或许可以说,这是人的认知的最大盲点。那么,为什么“问题”如此重要?因为“问题”是认知和行为的原点,围绕着“问题”整个思想才得以展开,也就是说,“问题”界定、打造了我们面对的现实,指引着我们行动的方向。

“P versus NP”之所以成为“世纪难题”,正是失足于“强调寻找正确的答案,而不是提出正确的问题”。

就NP而言,最初提出NP,是欲以其“不确定性”本质,区别于P的“确定性”本质。但是,流行的观念却是:NP=Nondeterministic Polynomial time,即“不确定性多项式时间”,而此定义是基于“不确定性图灵机(NDTM)”的,由于“不确定性图灵机”与“确定性图灵机(DTM)”等价,故此定义是“确定性”的P,而非“不确定性”的NP,至此,“不确定性”就从流行的NP问题中消失了,人们陷入了“NP=P?”的悖论,而不能自拔!

换句话说,将NP定义为“不确定性多项式时间”,意在强调寻找正确的答案,而忽略了提出的问题是否正确。为正本清源,将NP从“算法”层次还原到“问题”层次,我们提出NP的定义:NP=Nondeterministic Problem,即“不确定性问题”。

我们的这个NP定义,并不是仅仅换一个P的略写词,而是对“不确定性”这个术语的真正意义的确定化过程,本博客目前所介绍的内容,旨在算法理论层次上,理清“可计算性”意义上的“确定性”与“不确定性”的关系。“不确定性”这个概念的内涵,远远超过了算法理论这个层次,但在算法理论这个层次理清这个概念,无疑是最基本和最严格的工作。当然,这样的工作需大家参与、达成共识,这本身就是一项艰巨的集体性工作。

在此意义上,我们或许可以理解Hemaspaandra在介绍Gasarch的2012年“P versus NP”调查时的悲叹(http://blog.sciencenet.cn/blog-2322490-856768.html):

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。我希望在遥远的未来,当人们读到这四篇文章,可以帮助他们了解,在“P versus NP”还没得到解决的黑暗年代里人们的思想状态)




https://wap.sciencenet.cn/blog-2322490-893312.html

上一篇:点评《紐約客》文-流行的NP定义(2)
下一篇:NP的二种定义 - 实例分析和对比

3 杨正瓴 姜咏江 icgwang

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

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

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

GMT+8, 2022-1-25 07:37

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部