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

博文

按标题搜索
NP二个流行定义与“白马非马”
热度 2 2015-5-8 14:06
世纪难题“P versus NP”,通俗地讲,P代表计算机易解决的一类问题,NP代表计算机难解决的一类问题,“P versus NP”就是问:NP这类困难的问题到底能否被计算机有效解决(NP=P)?与此问题相关的研究,就形成了计算复杂性理论。 库克(Cook)1971年的那篇论文《The Complexity of Theorem Proving Procedures》,奠定了 ...
个人分类: 不确定性问题和算法讨论|3771 次阅读|3 个评论 热度 2
为什么还要讲“没用的NDTM”?(2)
热度 2 2015-5-3 14:58
我继续和同事对话: 同事:我认为,取消NDTM不会影响NP完备理论,只需将NP理论中涉及到用NDTM定义NP的陈述,改成用DTM在多项式时间内可验证的问题类,就可以了。 柳渝:那么,试看2000年柯克(Cook)为克雷数学研究所(CMI)介绍“P versus NP”所写的文章( http://www.claymath.org/sites/default/files/pvsnp.pdf ) ...
个人分类: 不确定性问题和算法讨论|2914 次阅读|3 个评论 热度 2
为什么还要讲“没用的NDTM”?(1)
热度 1 2015-5-2 14:58
最近我与一个工作在NP问题实际求解前沿的同事对话: 同事:我认为,如果取消了“不确定性图灵机(NonDeterministic Turing Machine NDTM)”这个概念,把NP定义成“确定性图灵机(Deterministic Turing Machine DTM)”在多项式时间内可验证的问题类,不会影响NP问题的实际求解,对NP完备理论也不会产生影响。 柳渝:此 ...
个人分类: 不确定性问题和算法讨论|3454 次阅读|1 个评论 热度 1
“问题”的系统观(整体观)
热度 1 2015-4-21 10:08
一,“问题”的中西文字源 1,英语( http://www.etymonline.com/index.php?term=problem ) “problem”,源自希腊语:proballo = pro (in face of) + ballo (to throw),指橫在起点与目标之间的“障礙”。 另外,“人问问题”又是无法避免的事实,于是,又有另一词“question”来表达,“question”源自中世纪的“审 ...
个人分类: 不确定性问题和算法讨论|3138 次阅读|2 个评论 热度 1
不确定性图灵机(NDTM)与“不确定性”
热度 7 2015-4-14 13:28
在NP完备理论(NP-completeness theory)中,把“不确定性图灵机”(NonDeterministic Turing Machine,NDTM)因一个问题存在多算法或多解而具有的“多选择”,当作了“不确定性问题(Nondeterministic Problem)”的“不确定性”,遂有用NDTM定义NP一说,这种观点的理论表达就是教科书中的流行概念:NP=不确定性多项式 ...
个人分类: 不确定性问题和算法讨论|7061 次阅读|28 个评论 热度 7
NP理论中几个术语的约定
热度 5 2015-4-10 10:24
于博文( http://blog.sciencenet.cn/blog-2322490-874183.html ),我们分析了NP二个定义涉及到二个内涵完全不同的“非确定型图灵机”,为了方便表达,我们提议约定几个术语的中文、英文及缩写: 一,术语的约定 TM (Turing Machine) = 图灵机 DTM (Deterministic Turing Machine) = 确定性图灵机 NTM (Non Turing ...
个人分类: 不确定性问题和算法讨论|4204 次阅读|12 个评论 热度 5
清明时节忆华工-法国诺莱特华工墓园
热度 6 2015-4-5 13:17
早就听说在我居住的亚眠市北边有一个欧洲最大的华工墓园:(Cimetière chinois de Nolette),但一直没机会去祭拜,前不久,结识了一个研究考古的同事,又说起此墓园,觉得应该去一趟了。 一天,读大三的儿子开车,我们一起来到这个离海边不远的墓园。墓园坐落在一片寂静田野中,入口是个白色雕花的大理石门,园内松柏青 ...
个人分类: 在中法文化之间流连|5221 次阅读|7 个评论 热度 6
参详P与NP的二个实例
热度 2 2015-3-31 11:00
P和NP指二个问题类。NP存在着二个流行定义(见Sipser的书“Introduction to the Theory of Computation”,Section 7.3[1]): 1,基于验证的定义:NP是“确定型图灵机”在多项式时间内可验证的语言类; 2,基于判定的定义:NP是“非确定型图灵机”在多项式时间内可接受的语言类。 于博文中( http://blog.sciencenet ...
个人分类: 不确定性问题和算法讨论|4037 次阅读|16 个评论 热度 2
井上靖先生的《孔子》
热度 2 2015-3-25 13:58
Jacques(我当年博士论文的导师)要去中国三个星期,我给他推荐了井上靖先生写的《孔子》,让他带在旅途中看。 不记得自己是应什么因缘读起这本书的,只记得翻开书的第一页,听主人翁蔫姜缓缓道来: - 先师孔子逝世时,我也追随别的弟子,在都城以北的泗水河畔孔子墓地结庐守孝三年。其后,我就移居到这偏远的山村里来 ...
个人分类: 在中法文化之间流连|3207 次阅读|5 个评论 热度 2
解读NDTM的概念偷换-NP定义中二个不同的NDTM
热度 6 2015-3-13 15:32
在计算复杂性理论中,NP是用“非确定型图灵机(nondeterministic Turing machine,NDTM)”来定义的,从“语言”的角度,存在着二个流行的定义(见 : Michael Sipser, Introduction to the Theory of Computation, Section 7.3): 1,基于验证的定义:NP是“确定型图灵机”在多项式时间内可验证的语言类; 2,基于判 ...
个人分类: 不确定性问题和算法讨论|4717 次阅读|25 个评论 热度 6

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

GMT+8, 2023-2-2 02:58

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部