科学网

 找回密码
  注册
NP是可计算的吗?- “算法”的二个层次
热度 3 柳渝 2015-12-30 17:26
于诸博文(注)我们解读流行观念“NP是可计算,但是难计算”,认为存在着认知错误,其根源在于人们未深究“算法”的本质(可计算性)。实际上,“算法”这一概念涉及到二个不同的层次:实例和问题,人们混淆了这二个层次,导致对“算法”概念的模糊。 这里,我们用下面的图帮助说明“算法”涉及到的二个层次: ...
个人分类: 不确定性问题和算法讨论|3559 次阅读|6 个评论 热度 3
NP是可计算的吗?- “问题”的分类
热度 4 柳渝 2015-12-16 16:03
在现有的NP完备理论(Theory of NP-Completeness)中,一个典型的观念就是:“NP是可计算,但是难计算的”,如此,就有如下的问题分类:                                 ...
个人分类: 不确定性问题和算法讨论|6896 次阅读|20 个评论 热度 4
什么是“判定问题”?(3)- NP-hard与NP
热度 1 柳渝 2015-12-1 12:19
我们已经从NP的二个定义等价的流行观点切入,通过解读NDTM、算法复杂度、停机问题,揭示了NP流行定义将NP与P混淆,导致NP的“不确定性”消失,是有“P versus NP”世纪难题的困惑。 这里,我们再来解读另一个重要概念NP-hard,进一步揭示NP流行定义带给人们观念认知的混淆和混乱: 一,流行观念:NP-hard 于流行观念 ...
个人分类: 不确定性问题和算法讨论|8492 次阅读|4 个评论 热度 1
什么是“判定问题”?(2)-悖论、停机问题与NP
热度 1 柳渝 2015-11-4 12:05
“判定问题 ” (德语entscheidungsproblem,英语decision problem)是可计算性理论的核心问题,由希尔伯特于1900年在巴黎第二届国际数学家大会上提出:是否存在这样一种确定的方法,在理论上可适用于任何假设,并且能够保证对无论是否正确的假设都能给出一个正确的结果?( https://zh.wikipedia.org/wiki/決定性問題 ) ...
个人分类: 不确定性问题和算法讨论|9037 次阅读|3 个评论 热度 1
自我否定与反思
热度 3 柳渝 2015-10-31 14:14
我们讨论了,“我在说谎”在逻辑上是悖论(不可说),但在日常语境中可说,是因为“主体”不同,前者是严格的(这句话),后者是含糊的,后者可以是说话的人,说话的人的“说”是对说话的人的肯定——不管这个人说了什么,换句话说,就是肯定了“我在说谎”这句话。 至于“我在说谎”表达的“否定”的内容,若在日常语境 ...
个人分类: 不确定性问题和算法讨论|3123 次阅读|5 个评论 热度 3
诗情画意的“NP”
热度 1 柳渝 2015-10-26 16:09
我的博客后面有很多师友的支持,NP的广泛性和深刻性使其带有某种神秘的色彩,实际上NP是我们生活中常见的现象,甚至可以说我们日常生活的本质就是NP,这正是我们这几篇博文所表达的,这些博文是大家交流的共同作品。 前面的博文说到悖论的本质不在“真”“假”,而是“不可说”,这种性质很有“艺术”气质(“人情味”) ...
个人分类: 不确定性问题和算法讨论|2436 次阅读|1 个评论 热度 1
解读“我在说谎”悖论(4)
热度 2 柳渝 2015-10-23 17:20
解读“我在说谎”悖论(3)中我们说:“我在说谎”之为悖论,在于严格的表达排除了自然语言不确定的人这个主体,主体成了这句话本身,所以“我在说谎”这句话的表达否定了这句话自己,成为逻辑意义上的悖论。 于是,我们可以问:为什么同样一句话“我在说谎”在自然语言中不构成悖论;而到了逻辑中就成了悖论? 网友 ...
个人分类: 不确定性问题和算法讨论|3081 次阅读|6 个评论 热度 2
索罗斯的“NP”观
热度 1 柳渝 2015-10-20 18:28
最近与朋友们谈NP理论,其中对证券市场颇有钻研的友人问:看过索罗斯写的“金融炼金术”,其中提到的“随机漫步假设”,是否是NP的另一种表现形式? 我们从NP理论的角度初步解读索罗斯的观点: 金融、证券市场已经成为今天政治和经济生活中最重要的组成部分,但它们运行的不稳定性(不可预测性)和操控的不确定性在事实 ...
个人分类: 不确定性问题和算法讨论|2653 次阅读|1 个评论 热度 1
关于NP讨论中的论域问题(2)
热度 1 柳渝 2015-10-16 23:21
图灵的“论可计算数及其在判定问题上的应用”(On Computable Numbers, With an Application to the Entscheidungsproblem)是1936年的工作,而他的博士论文“基于序数的逻辑系统”(Systems of Logic Based on Ordinals)是1938年完成的。前者可以说是计算机理论中的“圣经”,但后者却给理论和认知带来了很大的困惑,我们 ...
个人分类: 不确定性问题和算法讨论|3060 次阅读|1 个评论 热度 1
解读“我在说谎”悖论(3)
热度 2 柳渝 2015-10-15 13:44
我们继续讨论悖论的“自我否定”的意义,这里涉及到“我”,日常语言的“我”具有非常复杂的意义,“我是谁?”几乎是无法回答的,如果用“主体”来表达“我”,那么就可以讨论:“主体”如何说?说什么? 用自然语言说“我在说谎”,这时主体可以是“说话”的人,“我在说谎”就是主体说的话,这句话可“真”可“假”,对 ...
个人分类: 不确定性问题和算法讨论|2850 次阅读|16 个评论 热度 2

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

GMT+8, 2024-3-29 12:52

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部