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

博文

为什么还要讲“没用的NDTM”?(2)

已有 3510 次阅读 2015-5-3 14:58 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| NDTM, versus

我继续和同事对话:

同事:我认为,取消NDTM不会影响NP完备理论,只需将NP理论中涉及到用NDTM定义NP的陈述,改成用DTM在多项式时间内可验证的问题类,就可以了。

柳渝:那么,试看2000年柯克(Cook)为克雷数学研究所(CMI)介绍“P versus NP”所写的文章(http://www.claymath.org/sites/default/files/pvsnp.pdf)”,文章仍以NDTM定义NP开始,中间轻易过渡到DTM定义NP,其中又使用各种表达,如“求解”、“验证解”、“接受语言”、“判定问题”等,来陈述NP,却不对这些不同的表达加以层次的辨析和解释。于是,从认知的角度,与1971年那篇奠定NP理论的文章相比,30年后柯克对“P versus NP”的介绍,不是比1971年更清楚,而是更混乱了!

如果用DTM取代NDTM来定义NP,果真如此简单,为何学术界不改正而是维持、辯解理论上的混乱?

同事:使用NDTM定义NP,有其历史原因,而大家都承认DTM定义NP与NDTM定义NP等价,故有现在二个定义的混用。

柳渝:我们解读NP二个定义等价,指出此等价关系掩盖了NP的本质,正是希望引起人们的反思:在人们习以为常的观念中隐藏着认知偏差,也就是说,希望“聪明人”能“糊涂”起来,。。。



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

上一篇:为什么还要讲“没用的NDTM”?(1)
下一篇:NP二个流行定义与“白马非马”
收藏 IP: 82.246.87.*| 热度|

4 蔡小宁 杨正瓴 姜咏江 icgwang

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

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

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

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

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部