|||
我继续和同事对话:
同事:我认为,取消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的本质,正是希望引起人们的反思:在人们习以为常的观念中隐藏着认知偏差,也就是说,希望“聪明人”能“糊涂”起来,。。。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-23 17:04
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社