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

博文

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

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

于博文“点评《紐約客》文,兼答网友(1)(http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=891584)”,我们说:“P versus NP”的难度不在“答问题”,而在“问问题”,即认知层次上。结合“问题”的整体观(http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=884042),我们试着进一步阐释此观点。

从“问题”的整体观出发,“问题”涉及到二个层次:

1,认知层次:认知问题、定义问题(recognizing problem),于此层次,出现了新问题,而新问题还处在模糊不清状态,需要将之从已知的旧问题中辨识出来,故“问问题”。

2,行为层次:解决问题、求解问题(solving problem),于此层次,问题已辨识出来,指前进路上的“障碍”,需克服之,以达到目的,故“答问题”。

“问题”的这二个层次对应于中西文对“问题”的阐释,认知层次高于行为层次,二者是互补的关系。

于“P versus NP”,P是“可计算的”,是已知问题,而NP却是新问题。于是,首先须针对此新问题,“问问题”,即问:NP是什么?目的是将NP从P中分辨出来;然后才是针对分辨出来的NP,“答问题”,即解决:NP=P?

于是,我们可以看到,目前“P versus NP”的困境在“定义问题”,而不是“求解问题”,因为NP被定义成“图灵机在多项式时间可验证解的问题”,“可验证的”也是“可计算的”,即此NP本质是P。也就是说,将NP定义为“可验证的问题”,导致了其“不确定性”本质的消失,从而暗中肯定了“NP=P”,以至于“P versus NP”成为了悖论,乃至“世纪难题”,。。。

不幸的是,人们未意识到“P versus NP”难在“定义问题”:NP是什么?却一直纠结于“求解问题”:NP=P?,。。。

《紐約客》上的文章不仅是大众的好奇,更是专家的困惑,也正是作者所指出的这个问题在诸“千禧年”难题中的特殊性。




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

上一篇:点评《紐約客》文-流行的NP定义(1)
下一篇:点评《紐約客》文-流行的NP定义(3)
收藏 IP: 82.246.87.*| 热度|

4 杨正瓴 姜咏江 罗汉江 icgwang

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

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

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

GMT+8, 2024-11-23 04:53

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部