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

博文

传统定义的“非确定型图灵机”存在什么问题?——答网友

已有 3870 次阅读 2015-7-6 13:16 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记

迄今为止,传统定义的“非确定型图灵机”(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)中的评论:

-传统定义的非确定型图灵机,存在什么问题呢?  




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

上一篇:法国高考“法语”笔试(理科,经济社会科,2014年)
下一篇:NP是可计算的吗?- SAT问题
收藏 IP: 82.246.87.*| 热度|

3 杨正瓴 姜咏江 icgwang

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

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

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

GMT+8, 2024-4-25 14:18

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部