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

博文

NP是可计算的吗? - “问题”与“实例”

已有 4702 次阅读 2015-10-3 11:26 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| versus

流行观点“NP是可计算的”,所持的理由是:“NP存在指数时间算法”。

我们已从计算复杂性理论与可计算性理论相分离的现状、NDTM(nondeterministic Turing machine)与不确定性的关系、对“多项式时间”的误解等角度,解读了此流行观点导致NP的“不确定性消失”,致“P versus NP”成为世纪难题。这里,我们再从“问题”与“实例”的角度进一步解读对“NP存在指数时间算法”的误读:

于“实例”,对应的是“具体机器”层次,NP问题的某些“实例”可由NDTM计算,NDTM被定义为:在计算的每一时刻,进行到下一步骤有“多选择(several possibilities)”(A nondeterministic Turing machine is defined in the expected way. At any point in a computation the machine may proceed according to several possibilities. - Sipser's Introduction to the Theory of computation, p. 152)。NDTM与DTM(deterministic Turing machine)等价: Every nondeterministic Turing machine has an equivalent deterministic Turing machine(Sipser's Introduction to the Theory of computation, p. 152),也就是说,NDTM的本质是“确定性”,即NDTM所表达的“多选择”是“确定性”,而不能代表NP的本质“不确定性”,(见博文:http://blog.sciencenet.cn/blog-2322490-882297.html)。

然而于“问题”,对应“人”的层次,NP的“不确定性”表现为“不可判定(undecidable)”,换句话说,NP无法由NDTM及任何一种形式方式定义!

由此可见,于NP,“问题”与“实例”是二个层次完全不同的概念。一般来说,“实例”与“问题”的关系也就是常量与变量、具象与抽象、个别与一般的关系,二者相关并非总是等价的,比如,日常语言中说:保持公共场所卫生“人人有责”,但不说“人类有责”,因“人人有责”与“人类有责”相关但有别。同样,“NP问题实例可计算”,并不能推导出“NP可计算”,换句话说,说“NP存在指数时间算法”,只是指某些问题实例可计算,并不意味着任何一个问题实例都是可计算的。




https://wap.sciencenet.cn/blog-2322490-925012.html

上一篇:对“多项式时间复杂度”的误解
下一篇:解读“我在说谎”悖论(1)
收藏 IP: 82.246.87.*| 热度|

3 杨正瓴 icgwang nextvisionary

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

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

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

GMT+8, 2024-11-1 07:07

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部