|||
关于“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”的工作远未结束,。。。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-23 10:06
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社