什么是“判定问题”？（1）－ 可计算性理论与计算复杂性理论

热度 3 柳渝 2015-6-6 00:07

我们一直在解读，“P versus NP”之所以成为“世纪难题”，失足于NP定义：NP＝Nondeterministic Polynomial time（不确定性多项式时间），遂有流行观念“NP是多项式时间可验证的”，与此相关，还有一个流行观念“NP是可计算的”。这些观念直接导致计算复杂性理论（Computational complexity theory）与可计算性理论（Compu ...

个人分类: 不确定性问题和算法讨论|7712 次阅读|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（不确定性多项式时间） ...

个人分类: 不确定性问题和算法讨论|3876 次阅读|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）将要离世的时候，做出一个这样的结论：“在管理决策中最常见的错误，是我们强调寻找正确的答案，而不是 ...

个人分类: 不确定性问题和算法讨论|3693 次阅读|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 ...

个人分类: 不确定性问题和算法讨论|3780 次阅读|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)? 也就是人们所说的：是否所有可验证的问题都是算法可求解的问题？ 当然人 ...

个人分类: 不确定性问题和算法讨论|2778 次阅读|8 个评论 热度 2

关于NP讨论中的论域问题（1）

热度 2 柳渝 2015-5-14 18:03

1. 逻辑运算（真值表关系）与图灵机计算（可计算函数）具有不同的性质，但这两种不同的性质总是被混淆，它们的内涵更是被混乱。 2. 图灵机是普遍意义上的计算机模型，图灵机以抽象的物理结构表现了作为算法的“机械步骤”的结构和过程。图灵以图灵机的形式严格地表达了“不可判定问题”，这是图灵当时工作的主要目的，但 ...

个人分类: 不确定性问题和算法讨论|3439 次阅读|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》，奠定了 ...

个人分类: 不确定性问题和算法讨论|4206 次阅读|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 ） ...

个人分类: 不确定性问题和算法讨论|3223 次阅读|3 个评论 热度 2

为什么还要讲“没用的NDTM”？（1）

热度 1 柳渝 2015-5-2 14:58

最近我与一个工作在NP问题实际求解前沿的同事对话： 同事：我认为，如果取消了“不确定性图灵机（NonDeterministic Turing Machine NDTM）”这个概念，把NP定义成“确定性图灵机（Deterministic Turing Machine DTM）”在多项式时间内可验证的问题类，不会影响NP问题的实际求解，对NP完备理论也不会产生影响。 柳渝：此 ...

个人分类: 不确定性问题和算法讨论|3801 次阅读|1 个评论 热度 1

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