科学网

 找回密码
  注册
搜索
热搜: 科学 论文
搜索
解读“我在说谎”悖论(2)
热度 2 柳渝 2015-10-11 20:42
对悖论的一般解释是,因为“自我否定”,导致自相矛盾。如网友icgwang 分析“我在说谎”悖论所说:悖论本质上是同一性的自否定震荡属性,“真”是同一性的基础,“假”是自否定的条件。 这里,我们先对“自我否定”一说略作分析:通过“我在说谎”与“我在说真话”对照,我们看到二者的本质区别,“我在说谎”是悖论,这 ...
个人分类: 不确定性问题和算法讨论|2605 次阅读|6 个评论 热度 2
解读“我在说谎”悖论(1)
热度 6 柳渝 2015-10-10 12:18
解读NP涉及到对悖论的理解,而“我在说谎”是最简单、最经典而又具说明性的例子,此例子的解读将有助于理解“停机问题”,从而帮助理解NP的本质。 据文献资料,“我在说谎”悖论源于公元前六世纪,哲学家克利特人艾皮米尼地斯(Epimenides):“所有克利特人都说谎,他们中间的一个诗人这么说。” 《圣经》里也曾经提 ...
个人分类: 不确定性问题和算法讨论|4464 次阅读|20 个评论 热度 6
NP是可计算的吗? - “问题”与“实例”
热度 5 柳渝 2015-10-3 11:26
流行观点“NP是可计算的”,所持的理由是:“NP存在指数时间算法”。 我们已从计算复杂性理论与可计算性理论相分离的现状、NDTM(nondeterministic Turing machine)与不确定性的关系、对“多项式时间”的误解等角度,解读了此流行观点导致NP的“不确定性消失”,致“P versus NP”成为世纪难题。这里,我们再从“问题” ...
个人分类: 不确定性问题和算法讨论|3496 次阅读|36 个评论 热度 5
对“多项式时间复杂度”的误解
热度 3 柳渝 2015-9-12 22:33
在算法理论中,算法的“时间复杂度”并不是指计算具体问题的实际计算时间,而是指“渐进时间复杂度O(f(n))”,用来表达计算机的能力对问题的规模n的增长是否胜任,这里的“计算机的能力”或“问题的规模”不是“常量”,而是“变量”,指能力和规模的增长趋势,O(f(n))反应的是比值函数关系。 于“多项式时间复杂度”:O( ...
个人分类: 不确定性问题和算法讨论|6989 次阅读|8 个评论 热度 3
解读关于“多项式时间”的一个悖论
热度 3 柳渝 2015-9-2 11:33
网友们敏锐察觉到对“多项式时间”的解读是探讨“P versus NP”的一个重要议题,为此谈及一个旨在解读“多项式时间”的表达式(注): - 2^n=Cn,0+Cn,1+Cn,2+Cn,3+…+ Cn,n-1+ Cn,n 一方面,从组合数计数公式Cn,k=n(n-1)(n-2)…(n-k+1)/k!来看,Cn,k是一个k次多项式,其中k≤n,等式的右边是多项式,而等式的左边是指数 ...
个人分类: 不确定性问题和算法讨论|2919 次阅读|8 个评论 热度 3
世纪难题“P versus NP ”与金融市场的不确定性
柳渝 2015-8-22 13:55
暑假回国探亲访友,也是学术交流之旅,八月十九日,应深圳的一个“互联网金融云平台”IT公司的邀请,作了场题为“世纪难题P versus NP与金融市场的不确定性”的报告。 报告一方面介绍了我们的NP理论工作;另一方面,从NP理论的核心思想出发,展望了NP理论更广泛的基础和背景。经济活动中的“复杂性” 、“不稳定性”,特 ...
个人分类: 不确定性问题和算法讨论|1983 次阅读|没有评论
解析网友姜咏江的“k-CNF-SAT子句消去法”
热度 2 柳渝 2015-7-24 23:38
网友姜咏江提出“k-CNF-SAT子句消去法”,认为其算法的时间复杂度是“多项式时间”,从而一举解决了K-SAT问题。我们认为其中存在双重错误,一方面,模糊了“多项式时间”的“立场”,将多项式时间解决的“一维数组的搜索问题”(P)混淆为“K(K=3)-SAT问题”(NP);另一方面,将解决若干K-SAT问题实例混淆为解决K ...
个人分类: 不确定性问题和算法讨论|2873 次阅读|9 个评论 热度 2
NP是可计算的吗?- SAT问题
热度 3 柳渝 2015-7-17 16:14
目前为止,我们直接针对NP的流行定义:“NP是多项式时间可验证的问题”,解读其认知错误。我们指出,此认知错误来自于混淆了“nondeterministic Turing machine”二个不同的内涵:NTM(非图灵机)和NDTM(不确定性图灵机),从而得出NP二个定义等价,致NP的“不确定性”消失。 另外,还存在着一个更加令人困惑的流行观点 ...
个人分类: 不确定性问题和算法讨论|4937 次阅读|10 个评论 热度 3
传统定义的“非确定型图灵机”存在什么问题?——答网友
热度 1 柳渝 2015-7-6 13:16
迄今为止,传统定义的“非确定型图灵机”(NDTM),即我们称之的“不确定性图灵机”,存在的问题在于用NDTM定义的NP问题中没有了真正的“不确定性”,我们称之为“不确定性的消失”。NDTM以计算的“多选择”替代了问题本身的“不确定性”,肯定“可判定”就前提性地肯定了所定义的NP问题是P算法可判定的,所以我们认为流行 ...
个人分类: 不确定性问题和算法讨论|3011 次阅读|4 个评论 热度 1
对NP的误导和对NP的误解
热度 2 柳渝 2015-7-1 21:30
“P versus NP”成为世纪难题原因复杂。在理论上,专业学者混淆了P和NP的层次,将NP定义为“Non-deterministic Polynomial time,不确定性多项式时间)”,导致NP的本质“不确定性”的消失,此误导可追溯到Cook定理。 而一般对“P versus NP”感兴趣的大众学者,由于缺乏对NP与P的形式化定义的深入了解,往往以数学中 ...
个人分类: 不确定性问题和算法讨论|2540 次阅读|10 个评论 热度 2

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

GMT+8, 2021-12-6 17:36

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部