不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

按标题搜索
与法国朋友漫谈P vs NP(5)
2020-5-20 20:09
柳渝: 我用 “imaginaire (想象) ” 一词指如您所说 “ 有些微妙 ” 的 NDTM ,确实容易产生歧义。实际上,大致存在三种对 NDTM 的解释: - NDTM 具有无限的并行能力; - NDTM 可用 TM 在指数时间模拟; - Oracle ( Cook 原始关于 NDTM 的定义)。 ...
个人分类: 不确定性问题和算法讨论|1719 次阅读|没有评论
与法国朋友漫谈P vs NP(4)
2020-5-20 19:51
柳渝: 是的,我期待一个与常识认知一致的 NP 定义,但并不排除直觉: “ 除了明显的直觉和必要的推理外,人们没有其他方法可以了解真相。 ” - 笛卡尔 您解释 NP 的形式化定义: - 定义 1: NP 是不确定性图灵机多项式时间可判定的问题。 问题是这里的 “ 不确定性图灵机 ” ...
个人分类: 不确定性问题和算法讨论|1696 次阅读|没有评论
与法国朋友漫谈P vs NP(3)
热度 1 2020-5-20 12:17
与法国朋友漫谈P vs NP缘起于Youtube上一个很受欢迎的法语普及 P vs NP 的视频【 1 】,所以我直接和此视频制作者Passe-Science对话。我将对话译成中文分享: 柳渝: 我提一个问题: 您举了 3 个 NP 问题的例子: 3- 图染色问题,背包问题,合取范式可满足问题( SAT 问题) ...
个人分类: 不确定性问题和算法讨论|1867 次阅读|1 个评论 热度 1
与法国朋友漫谈P vs NP(2)
2020-5-18 17:31
现在我回到 P vs NP 。 通俗说, P ( Polynomial )指计算机求解容易的问题,即存在多项式时间精确算法,比如 GPS 中寻找任意二个地点之间的最短距离。 NP ( Non-deterministic Polynomial )指计算机求解困难的问题,比如视频举的 3 个例子: 3- 图染色问题,背包问题,合取范 ...
个人分类: 不确定性问题和算法讨论|2011 次阅读|没有评论
与法国朋友漫谈P vs NP(1)
2020-5-16 16:18
同事 Didier 是我多年的同事好友, Louis 是大学经济系退休教师,对我的 P vs NP 问题研究感兴趣,有了如下对话。 首先 Didier 给 Louis 推荐了一个很受欢迎的法语普及 P vs NP 的视频【 1 】。 然后,给 Louis 作了一些介绍,我接着说: 这个视频很好!可惜他用逻辑和数学的方法 ...
个人分类: 不确定性问题和算法讨论|2124 次阅读|没有评论
Alan Cobham,计算复杂性理论奠基者之一
2020-4-26 15:12
Alan Cobham ( 1927 - 2011 )是最早提出 “ 多项式时间复杂度问题类 P” 的学者之一 ,他 1965 年的文章 “The Intrinsic Computational Difficulty of Functions(函数计算的内在难度 )” 被认为是计算复杂性理论的重要论文之一,被 Cook 在其 1971 年的著名论文 “The complexity of theor ...
个人分类: 不确定性问题和算法讨论|2058 次阅读|没有评论
NP是可判定的吗?- 集合与判断
热度 1 2020-2-29 12:34
目录 一,NP的形式化定义 二,集合与判断 三,人的判断 四,算法的判断 五,分析 NP 形式定义 六,质疑 NP NP 的形式定义是用集合表达的,为了进一步理解 NP ,让我们回到对 “ 集合 ” 这个基本概念的理解上。 一,NP的形式化定义 NP 存在二个被认为等价的 ...
个人分类: 不确定性问题和算法讨论|5247 次阅读|5 个评论 热度 1
库克“定理”还是库克“定义”(NP)?
热度 1 2020-1-29 22:19
确实,我们写在这里是一种 “ 观察 ” ,但却是一个认识:为什么复杂性理论与对 NP 的知识之间存在巨大差别? — 一个理论的专业性不应该是人们认知错误的来源。 我们探讨了库克的论文 “ 理论证明过程中的复杂性 ” ( The Complexity of Theorem-Proving Procedures ),论文摘要中宣称:论 ...
个人分类: 不确定性问题和算法讨论|2714 次阅读|1 个评论 热度 1
“不确定性问题”(Nondeterministic Problem,NP)与"哥德尔不完全定理“
热度 3 2020-1-1 05:36
“不确定性问题”(Nondeterministic Problem,NP)与“哥德尔不完全定理” - 周剑铭,柳渝 1931 年哥德尔证明:任何无矛盾的公理体系,只要包含初等算术的陈述,则必定存在一个不可判定命题,用这组公理不能判定其真假。 虽然哥德尔不完全定理只是针对包含数论的公理体系而言的,由于人 ...
个人分类: 不确定性问题和算法讨论|7755 次阅读|7 个评论 热度 3
关于“整体大于部分之和”的讨论
热度 2 2019-12-15 13:02
Jean-Paul Delahaye 是法国里尔( Lille) 大学计算机系的教授,也是法国《 科学月刊》杂志的 “ 逻辑和计算 ” 栏目的编辑。《科学月刊》是法国著名的科普期刊,成立于 1977 年,与《科学美国人》月刊相当。 在《科学月刊》上, Jean-Paul Delahaye 发表了一篇题为 “ 整体大于部分之和 ” ...
个人分类: 不确定性问题和算法讨论|6674 次阅读|3 个评论 热度 2

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

GMT+8, 2024-3-29 19:42

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部