科学网—liuyu2205的博文 - 第8页

设为首页收藏本站

开启辅助访问切换到宽版

科学网 › 我的中心 › 博文 › liuyu2205的博文

liuyu2205

https://blog.sciencenet.cn/?2322490

在中法文化之间流连| 不确定性问题和算法讨论| 智能哲学| NP理论| 非经典逻辑与中国传统逻辑| 英语博文| 图灵论著专研与精译工作群| AI伦理与社会群| 周剑铭论中国思想与中西文化系列文章| 在法国教逻辑课| 教学中的文化视角| 师徒对话| Paul Jorion的书译文| 解读哥德尔不完全性定理| 波普尔的《科学发现的逻辑》| 《易经》学习| 系统思维|

解读“我在说谎”悖论（2）: 热度 2 柳渝 2015-10-11 20:42; 对悖论的一般解释是，因为“自我否定”，导致自相矛盾。如网友icgwang 分析“我在说谎”悖论所说：悖论本质上是同一性的自否定震荡属性，“真”是同一性的基础，“假”是自否定的条件。这里，我们先对“自我否定”一说略作分析：通过“我在说谎”与“我在说真话”对照，我们看到二者的本质区别，“我在说谎”是悖论，这 ...; 个人分类: 不确定性问题和算法讨论|3368 次阅读|6 个评论热度 2

解读“我在说谎”悖论（1）: 热度 6 柳渝 2015-10-10 12:18; 解读NP涉及到对悖论的理解，而“我在说谎”是最简单、最经典而又具说明性的例子，此例子的解读将有助于理解“停机问题”，从而帮助理解NP的本质。据文献资料，“我在说谎”悖论源于公元前六世纪，哲学家克利特人艾皮米尼地斯（Epimenides）：“所有克利特人都说谎，他们中间的一个诗人这么说。” 《圣经》里也曾经提 ...; 个人分类: 不确定性问题和算法讨论|7093 次阅读|20 个评论热度 6

NP是可计算的吗？－ “问题”与“实例”: 热度 5 柳渝 2015-10-3 11:26; 流行观点“NP是可计算的”，所持的理由是：“NP存在指数时间算法”。我们已从计算复杂性理论与可计算性理论相分离的现状、NDTM（nondeterministic Turing machine）与不确定性的关系、对“多项式时间”的误解等角度，解读了此流行观点导致NP的“不确定性消失”，致“P versus NP”成为世纪难题。这里，我们再从“问题” ...; 个人分类: 不确定性问题和算法讨论|4422 次阅读|36 个评论热度 5

对“多项式时间复杂度”的误解: 热度 3 柳渝 2015-9-12 22:33; 在算法理论中，算法的“时间复杂度”并不是指计算具体问题的实际计算时间，而是指“渐进时间复杂度O(f(n))”，用来表达计算机的能力对问题的规模n的增长是否胜任，这里的“计算机的能力”或“问题的规模”不是“常量”，而是“变量”，指能力和规模的增长趋势，O(f(n))反应的是比值函数关系。于“多项式时间复杂度”：O( ...; 个人分类: 不确定性问题和算法讨论|9741 次阅读|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，等式的右边是多项式，而等式的左边是指数 ...; 个人分类: 不确定性问题和算法讨论|3778 次阅读|8 个评论热度 3

世纪难题“P versus NP ”与金融市场的不确定性: 柳渝 2015-8-22 13:55; 暑假回国探亲访友，也是学术交流之旅，八月十九日，应深圳的一个“互联网金融云平台”IT公司的邀请，作了场题为“世纪难题P versus NP与金融市场的不确定性”的报告。报告一方面介绍了我们的NP理论工作；另一方面，从NP理论的核心思想出发，展望了NP理论更广泛的基础和背景。经济活动中的“复杂性” 、“不稳定性”，特 ...; 个人分类: 不确定性问题和算法讨论|2539 次阅读|没有评论

解析网友姜咏江的“k-CNF-SAT子句消去法”: 热度 2 柳渝 2015-7-24 23:38; 网友姜咏江提出“k-CNF-SAT子句消去法”，认为其算法的时间复杂度是“多项式时间”，从而一举解决了K－SAT问题。我们认为其中存在双重错误，一方面，模糊了“多项式时间”的“立场”，将多项式时间解决的“一维数组的搜索问题”（P）混淆为“K（K=3）－SAT问题”（NP）；另一方面，将解决若干K－SAT问题实例混淆为解决K ...; 个人分类: 不确定性问题和算法讨论|3548 次阅读|9 个评论热度 2

NP是可计算的吗？－ SAT问题: 热度 3 柳渝 2015-7-17 16:14; 目前为止，我们直接针对NP的流行定义：“NP是多项式时间可验证的问题”，解读其认知错误。我们指出，此认知错误来自于混淆了“nondeterministic Turing machine”二个不同的内涵：NTM（非图灵机）和NDTM（不确定性图灵机），从而得出NP二个定义等价，致NP的“不确定性”消失。另外，还存在着一个更加令人困惑的流行观点 ...; 个人分类: 不确定性问题和算法讨论|6167 次阅读|10 个评论热度 3

传统定义的“非确定型图灵机”存在什么问题？——答网友: 热度 1 柳渝 2015-7-6 13:16; 迄今为止，传统定义的“非确定型图灵机”（NDTM），即我们称之的“不确定性图灵机”，存在的问题在于用NDTM定义的NP问题中没有了真正的“不确定性”，我们称之为“不确定性的消失”。NDTM以计算的“多选择”替代了问题本身的“不确定性”，肯定“可判定”就前提性地肯定了所定义的NP问题是P算法可判定的，所以我们认为流行 ...; 个人分类: 不确定性问题和算法讨论|3865 次阅读|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的形式化定义的深入了解，往往以数学中 ...; 个人分类: 不确定性问题和算法讨论|3441 次阅读|10 个评论热度 2

1 ... 2 3 4 5 6 789 10 11 下一页

会议

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

GMT+8, 2024-4-19 09:27

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部