科学网

 找回密码
  注册
“问题”的系统观(整体观)
热度 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”源自中世纪的“审 ...
个人分类: 不确定性问题和算法讨论|3522 次阅读|2 个评论 热度 1
不确定性图灵机(NDTM)与“不确定性”
热度 7 柳渝 2015-4-14 13:28
在NP完备理论(NP-completeness theory)中,把“不确定性图灵机”(NonDeterministic Turing Machine,NDTM)因一个问题存在多算法或多解而具有的“多选择”,当作了“不确定性问题(Nondeterministic Problem)”的“不确定性”,遂有用NDTM定义NP一说,这种观点的理论表达就是教科书中的流行概念:NP=不确定性多项式 ...
个人分类: 不确定性问题和算法讨论|8011 次阅读|28 个评论 热度 7
NP理论中几个术语的约定
热度 5 柳渝 2015-4-10 10:24
于博文( http://blog.sciencenet.cn/blog-2322490-874183.html ),我们分析了NP二个定义涉及到二个内涵完全不同的“非确定型图灵机”,为了方便表达,我们提议约定几个术语的中文、英文及缩写: 一,术语的约定 TM (Turing Machine) = 图灵机 DTM (Deterministic Turing Machine) = 确定性图灵机 NTM (Non Turing ...
个人分类: 不确定性问题和算法讨论|4783 次阅读|12 个评论 热度 5
参详P与NP的二个实例
热度 2 柳渝 2015-3-31 11:00
P和NP指二个问题类。NP存在着二个流行定义(见Sipser的书“Introduction to the Theory of Computation”,Section 7.3[1]): 1,基于验证的定义:NP是“确定型图灵机”在多项式时间内可验证的语言类; 2,基于判定的定义:NP是“非确定型图灵机”在多项式时间内可接受的语言类。 于博文中( http://blog.sciencenet ...
个人分类: 不确定性问题和算法讨论|4528 次阅读|16 个评论 热度 2
解读NDTM的概念偷换-NP定义中二个不同的NDTM
热度 6 柳渝 2015-3-13 15:32
在计算复杂性理论中,NP是用“非确定型图灵机(nondeterministic Turing machine,NDTM)”来定义的,从“语言”的角度,存在着二个流行的定义(见 : Michael Sipser, Introduction to the Theory of Computation, Section 7.3): 1,基于验证的定义:NP是“确定型图灵机”在多项式时间内可验证的语言类; 2,基于判 ...
个人分类: 不确定性问题和算法讨论|5351 次阅读|25 个评论 热度 6
在贡比涅大学作报告
热度 3 柳渝 2015-2-5 12:23
周一(2015/2/2)到贡比涅大学(Université de Technologie de Compiègne)作报告去了。 法国高等教育体制有别于欧洲及美国,分:大学校(Grandes Ecoles)和公立综合大学(Université)。“公立综合大学”属于大众化教育机构,在校生占全国大学生的80%-90%,学生没有入学考试,通过高中毕业会考,就有资格就读, 但一、 ...
个人分类: 不确定性问题和算法讨论|4525 次阅读|8 个评论 热度 3
我们为什么说“确定型图灵机”不是“非确定型图灵机”的特例?
热度 3 柳渝 2015-1-27 16:52
将“确定型图灵机”理解为“非确定型图灵机”的特例是非常流行的观点,我们已经分析了这种情况导致“不确定性”的消失,即在NP完备理论(NP-completeness theory)中始终存在着事先暗中肯定:NP=P,这种认知上的错误。只要你“认为”非确定型图灵机包含了确定型图灵机,就意味着事先“承诺(注)”了非确定型图灵机与确 ...
个人分类: 不确定性问题和算法讨论|5386 次阅读|8 个评论 热度 3
什么是Cook's Theorem?
热度 1 柳渝 2015-1-11 23:03
It is in the admission of ignorance and the admission of uncertainty that there is a hope for the continuous motion of human beings in some direction that doesn't get confined, permanently blocked, as it has so many times before in various periods in the history of man. - Richard P. Feynman (19 ...
个人分类: 不确定性问题和算法讨论|3308 次阅读|2 个评论 热度 1
NP是可计算的吗?- 常量与变量关系中的认知层次问题
热度 3 柳渝 2015-1-9 14:14
网友姜咏江的博文“美国克雷数学研究所会不会颁奖? http://blog.sciencenet.cn/home.php?mod=spaceuid=340399do=blogid=849311 ”,通过辨析常量与变量不同,说明NP问题定义的流行观念中可能存在着的悖论。 此文涉及到二个常见的算法问题: 1,搜索问题( http://zh.wikipedia.org/zh/計算複雜性理論 ):任给 ...
个人分类: 不确定性问题和算法讨论|3388 次阅读|6 个评论 热度 3
“判断”的层次
热度 1 柳渝 2015-1-7 18:15
“判断”是人最基本的思维活动之一。 于汉字(汉字基因): 判═半刀,分也,辨也,斷也; 斷═絲斧,使不連續,折也,判也,絕也,無也。 判斷者,分辨後令之不再連續也。 按西方哲学的传统观念,也是人们现在普遍接受的观念,人的思维活动包括:概念、判断、推理。为此,我们引用在西方语言、逻辑学中占有重要地位的书 ...
个人分类: 不确定性问题和算法讨论|3726 次阅读|3 个评论 热度 1

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

GMT+8, 2024-3-29 01:07

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部