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

博文

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

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

关于“P versus NP”,流行的问法如《紐約客》文中(http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=891301)所述:Does P (problems that we can easily solve) equal NP (problems that we can easily check)?

也就是人们所说的:是否所有可验证的问题都是算法可求解的问题?

当然人们可以这样提问,而且直觉上人们普遍都能接受:NP ≠ P,如Aaronson的the philosophical argument:

-“If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.”

但是,几十年来,对“NP ≠ P”这样的认知,人们始终未能进行理性和科学的分析,“P versus NP”遂成为了越来越难解的“世纪难题”。我们的观点是,“P versus NP”流行的问法本身存在着认知偏差,也就是我们在博文中试着反复解读的,NP流行定义存在着认知偏差,即将NP定义为“可验证的问题”,导致了NP的“不确定性”本质消失,从而暗中肯定了“NP=P”,以至于“P versus NP”成为了悖论,乃至“世纪难题”,。。。

所以,“P versus NP”的难度不在“答问题”,而在“问问题”,即认知层次上。这些需要在讨论中逐步揭示和领悟,也就是说,解读“P versus NP”的工作远未结束,。。。  




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

上一篇:关于NP讨论中的论域问题(1)
下一篇:点评《紐約客》文-流行的NP定义(2)
收藏 IP: 82.246.87.*| 热度|

4 蔡小宁 姜咏江 杨正瓴 icgwang

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

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

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

GMT+8, 2024-12-23 21:26

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部