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

博文

什么是“判定问题”?(1)- 可计算性理论与计算复杂性理论

已有 6226 次阅读 2015-6-6 00:07 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| versus, 计算复杂性理论, 可计算性理论

我们一直在解读,“P versus NP”之所以成为“世纪难题”,失足于NP定义:NP=Nondeterministic Polynomial time(不确定性多项式时间),遂有流行观念“NP是多项式时间可验证的”,与此相关,还有一个流行观念“NP是可计算的”。这些观念直接导致计算复杂性理论(Computational complexity theory)与可计算性理论(Computability theory)相分离,作为计算复杂性理论基础的NP完备理论(NP-completeness theory),就成了无源之水,无本之木!

于可计算性理论,按人们一般的理解,顾名思义是研究“可计算性”,即研究哪些问题是可计算的,然而,若追本溯源,可以看到,此理论的目的是通过“可计算性”,研究与之相对的“不可判定性”。“可计算性”概念源于古老的西方哲学问题:思维机械化,其中心议题是设想通过将思维表达成计算,来检验和消除认知错误,正如莱布尼茨所说:

- 纠正我们推理的唯一方式是使它们同数学一样准确、明晰,这样我们能一眼看出我们的错误,并且在人们有争执的时候,可以简单的说,让我们计算「calculemus」,而无须进一步的忙乱,就能看出谁是正确的。(The only way to rectify our reasonings is to make them as tangible as those of the Mathematicians, so that we can find our error at a glance, and when there are disputes among persons, we can simply say: Let us calculate [calculemus], without further ado, to see who is right.)

于20世纪初,希尔伯特正式提出了利用计算机彻底系统解决所有数学问题的计划,其中的希尔伯特第10问题,又称“丢番图方程问题”,即探究求解任意的丢番图方程的算法的存在性。然而,哥德尔几乎在同时提出了“哥德尔不完备定理”,证明了不存在着这样的算法,它能正确回答有关初等数论的全部问题。接着,图灵进一步提出普遍意义上的计算机模型-“图灵机”,严格证明了不存在这样的图灵机,一般性地表达为“判定问题(Decision Problem)”,由此形成了可计算性理论的核心内容。

于20世纪40年代,发明了基于冯·诺伊曼结构的实际计算机,计算机应用广泛开展起来,于实际应用中出现了一些计算困难的问题,“计算复杂性理论”于此创生。一般说来,计算复杂性理论研究“复杂性”,即研究那些计算困难问题的“复杂性”,库克(Cook)于1971年的那篇论文《The Complexity of Theorem Proving Procedures》,引入“Nondeterministic Turing machine(NDTM)”,将那些计算困难的问题定义为NP(Nondeterministic Polynomial time),由于NDTM的本质是图灵机(TM),遂有诸如“NP是多项式时间可验证的”、“NP是可计算的”的流行观念,其相关理论称之“NP完备理论”。

由此可见,原本NP的提出是针对计算困难的问题,与P相对,然而NP的流行观念混淆了NP与P的本质区别,导致NP的本质“不确定性”消失,是有计算复杂性理论与可计算性理论完全脱节,这是造成现有的NP完备理论严重困难的最根本性的原因。




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

上一篇:NP的二种定义 - 实例分析和对比
下一篇:漫谈“汉字”(6)- “緣”

3 姜咏江 杨正瓴 icgwang

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

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

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

GMT+8, 2022-1-25 07:49

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部