||
迄今为止,传统定义的“非确定型图灵机”(NDTM),即我们称之的“不确定性图灵机”,存在的问题在于用NDTM定义的NP问题中没有了真正的“不确定性”,我们称之为“不确定性的消失”。NDTM以计算的“多选择”替代了问题本身的“不确定性”,肯定“可判定”就前提性地肯定了所定义的NP问题是P算法可判定的,所以我们认为流行定义的NP问题实质都是P问题。由此可以说,所有在这些定义基础上,正在进行P=NP证明或宣称已经证明了P=NP的人,只不过是证明了P=P,与真正的NP无涉 —— 这种难以自拔的自信,正是由这种“NP问题”的定义误导而产生的对NP的误解。还应当看到,现有的教科书中对这些基本概念的灌输继续在误导学生,死记这些定义的学生学了后基本都丢弃了,而有心深入的人却往往困惑或被误导而不能自拔,这二者都造成了智力上很大的浪费。
我们从“NP问题的两个定义是等价的”,即“NP是多项式时间确定性图灵机可验证的”等价于“NP是多项式时间不确定性图灵机可判定的”的流行观点切入,揭示这两个定义存在着“不确定性图灵机”的内涵上的偷换,“两个NP问题的定义的等价”是层次上的混淆和意义上的混乱,。。。具体的分析可见我的博客上发布的文章及有关讨论。我们NP理论的进一步深入阐述,待以后逐步开展。
附:qingshanren网友的提问来自博文“实例分析和对比二种NP定义”(http://blog.sciencenet.cn/home.php?mod=space&uid=2322490&do=blog&id=894021&cid=4119142&goto=new#comment_4119142_li)中的评论:
-传统定义的非确定型图灵机,存在什么问题呢?
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-27 12:48
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社