科学网

 找回密码
  注册
搜索
热搜: 科学 论文
搜索
什么是“判定问题”?(1)- 可计算性理论与计算复杂性理论
热度 3 柳渝 2015-6-6 00:07
我们一直在解读,“P versus NP”之所以成为“世纪难题”,失足于NP定义:NP=Nondeterministic Polynomial time(不确定性多项式时间),遂有流行观念“NP是多项式时间可验证的”,与此相关,还有一个流行观念“NP是可计算的”。这些观念直接导致计算复杂性理论(Computational complexity theory)与可计算性理论(Compu ...
个人分类: 不确定性问题和算法讨论|6032 次阅读|11 个评论 热度 3
NP的二种定义 - 实例分析和对比
热度 2 柳渝 2015-5-29 18:13
至此,针对流行的NP定义:NP=Nondeterministic Polynomial time,我们提出了新的NP定义:NP=Nondeterministic Problem。 这里,我们用Sisper书(Introduction to the Theory of Computation)中的二个实例来分析和对比这二种定义。 一,二种NP定义 1,NP=Nondeterministic Polynomial time(不确定性多项式时间) ...
个人分类: 不确定性问题和算法讨论|2905 次阅读|8 个评论 热度 2
点评《紐約客》文-流行的NP定义(3)
热度 3 柳渝 2015-5-26 20:39
“The most serious mistakes are not being made as a result of wrong answers. The true dangerous thing is asking the wrong question.” ― Peter Drucker 现代管理学之父彼得•德鲁克(Peter Drucker)将要离世的时候,做出一个这样的结论:“在管理决策中最常见的错误,是我们强调寻找正确的答案,而不是 ...
个人分类: 不确定性问题和算法讨论|2968 次阅读|7 个评论 热度 3
点评《紐約客》文-流行的NP定义(2)
热度 1 柳渝 2015-5-22 10:54
于博文“点评《紐約客》文,兼答网友(1)( http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogid=891584 )”,我们说:“P versus NP”的难度不在“答问题”,而在“问问题”,即认知层次上。结合“问题”的整体观( http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogi ...
个人分类: 不确定性问题和算法讨论|3170 次阅读|2 个评论 热度 1
点评《紐約客》文-流行的NP定义(1)
热度 2 柳渝 2015-5-20 21:30
关于“P versus NP”,流行的问法如《紐約客》文中( http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogid=891301 )所述:Does P (problems that we can easily solve) equal NP (problems that we can easily check)? 也就是人们所说的:是否所有可验证的问题都是算法可求解的问题? 当然人 ...
个人分类: 不确定性问题和算法讨论|2159 次阅读|8 个评论 热度 2
关于NP讨论中的论域问题(1)
热度 2 柳渝 2015-5-14 18:03
1. 逻辑运算(真值表关系)与图灵机计算(可计算函数)具有不同的性质,但这两种不同的性质总是被混淆,它们的内涵更是被混乱。 2. 图灵机是普遍意义上的计算机模型,图灵机以抽象的物理结构表现了作为算法的“机械步骤”的结构和过程。图灵以图灵机的形式严格地表达了“不可判定问题”,这是图灵当时工作的主要目的,但 ...
个人分类: 不确定性问题和算法讨论|2725 次阅读|10 个评论 热度 2
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》,奠定了 ...
个人分类: 不确定性问题和算法讨论|3274 次阅读|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 ) ...
个人分类: 不确定性问题和算法讨论|2561 次阅读|3 个评论 热度 2
为什么还要讲“没用的NDTM”?(1)
热度 1 柳渝 2015-5-2 14:58
最近我与一个工作在NP问题实际求解前沿的同事对话: 同事:我认为,如果取消了“不确定性图灵机(NonDeterministic Turing Machine NDTM)”这个概念,把NP定义成“确定性图灵机(Deterministic Turing Machine DTM)”在多项式时间内可验证的问题类,不会影响NP问题的实际求解,对NP完备理论也不会产生影响。 柳渝:此 ...
个人分类: 不确定性问题和算法讨论|2963 次阅读|1 个评论 热度 1

本页有 1 篇博文因作者的隐私设置或未通过审核而隐藏

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

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

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部