科学网

 找回密码
  注册
搜索
热搜: 科学 论文
搜索
点评《紐約客》文-流行的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)将要离世的时候,做出一个这样的结论:“在管理决策中最常见的错误,是我们强调寻找正确的答案,而不是 ...
个人分类: 不确定性问题和算法讨论|3055 次阅读|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 ...
个人分类: 不确定性问题和算法讨论|3236 次阅读|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)? 也就是人们所说的:是否所有可验证的问题都是算法可求解的问题? 当然人 ...
个人分类: 不确定性问题和算法讨论|2210 次阅读|8 个评论 热度 2
关于NP讨论中的论域问题(1)
热度 2 柳渝 2015-5-14 18:03
1. 逻辑运算(真值表关系)与图灵机计算(可计算函数)具有不同的性质,但这两种不同的性质总是被混淆,它们的内涵更是被混乱。 2. 图灵机是普遍意义上的计算机模型,图灵机以抽象的物理结构表现了作为算法的“机械步骤”的结构和过程。图灵以图灵机的形式严格地表达了“不可判定问题”,这是图灵当时工作的主要目的,但 ...
个人分类: 不确定性问题和算法讨论|2813 次阅读|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》,奠定了 ...
个人分类: 不确定性问题和算法讨论|3383 次阅读|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 ) ...
个人分类: 不确定性问题和算法讨论|2634 次阅读|3 个评论 热度 2
为什么还要讲“没用的NDTM”?(1)
热度 1 柳渝 2015-5-2 14:58
最近我与一个工作在NP问题实际求解前沿的同事对话: 同事:我认为,如果取消了“不确定性图灵机(NonDeterministic Turing Machine NDTM)”这个概念,把NP定义成“确定性图灵机(Deterministic Turing Machine DTM)”在多项式时间内可验证的问题类,不会影响NP问题的实际求解,对NP完备理论也不会产生影响。 柳渝:此 ...
个人分类: 不确定性问题和算法讨论|3075 次阅读|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”源自中世纪的“审 ...
个人分类: 不确定性问题和算法讨论|2737 次阅读|2 个评论 热度 1
不确定性图灵机(NDTM)与“不确定性”
热度 7 柳渝 2015-4-14 13:28
在NP完备理论(NP-completeness theory)中,把“不确定性图灵机”(NonDeterministic Turing Machine,NDTM)因一个问题存在多算法或多解而具有的“多选择”,当作了“不确定性问题(Nondeterministic Problem)”的“不确定性”,遂有用NDTM定义NP一说,这种观点的理论表达就是教科书中的流行概念:NP=不确定性多项式 ...
个人分类: 不确定性问题和算法讨论|5783 次阅读|28 个评论 热度 7

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

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

GMT+8, 2022-1-26 14:09

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部