科学网

 找回密码
  注册
NP与“不确定性原理“
热度 2 柳渝 2019-9-7 18:46
本博客名称为 “ 不确定性的困惑与 NP 理论 ” ,前期一直致力于介绍我们基于 Entscheidungsproblem 理论定义的“ NP ( Nondeterministic Problem )”与基于流行的 NDTM 定义的“NP( Nondeterministic Polynomial-Time, 不确定性多项式时间 )”的本质研究,提供了对 “P vs NP” 问题全新的视角 ...
个人分类: 不确定性问题和算法讨论|6220 次阅读|2 个评论 热度 2
“阿蒂亚发布证明‘黎曼猜想’”前后及意义
热度 4 柳渝 2018-9-25 17:21
“黎曼猜想(Riemann hypothesis)”与“P vs NP问题”都被克雷数学所评为“世纪七大数学难题”之一。 菲尔兹奖和阿贝尔奖获得者阿蒂亚(Michael Atiyah)爵士于9月24日在海德堡诺贝尔奖获得者论坛上发布,他证明了世纪七大数学难题之一的“黎曼猜想”,但使大多事前感到兴奋的人失望,因为构成他的证明的主要理论包括他 ...
个人分类: 不确定性问题和算法讨论|9051 次阅读|7 个评论 热度 4
关于“P vs NP”的讨论(3)
柳渝 2017-12-16 19:30
我们继续和大家分享这次关于P vs NP讨论的第三部分,希望对此议题感兴趣的网友能对其中所蕴含的认知方面的问题有所思考。 我们的NP理论工作起于对流行NP定义的质疑和解读,在此基础上我们认为计算复杂性理论的“P问题”实际上就是可计算性理论的“可计算性问题(确定性问题)”,由此相对于P我们来认知NP,其定义自然为“ ...
个人分类: 不确定性问题和算法讨论|3204 次阅读|没有评论
关于“P vs NP”的讨论(2)
柳渝 2017-12-9 12:23
我与Y君围绕着“P vs NP”继续讨论,逐渐将讨论的焦点集中在由NDTM定义的NP上,Y君提出一个“密码锁问题”,大家通过判断“密码锁”是P还是NP来考察NP的定义。 继续分享我们的部分对话: 一,对话(2017/11/22) Y君: 看了你的最新博文。感到你是在这个地方有问题: 你说:追本溯源,NP欲指“与P相对的NP”,即“P指 ...
个人分类: 不确定性问题和算法讨论|3809 次阅读|没有评论
关于“P vs NP”的讨论(1)
热度 2 柳渝 2017-12-5 20:47
最近和几个网友展开了富有成效的关于“P vs NP”的讨论,我把讨论的主要内容整理成文与大家分享,希望对此议题感兴趣的网友能对其中所蕴含的认知方面的基本问题有所思考。 借此讨论我们进一步阐释我们NP理论工作的基本观点:我们不是反对P和NP术语,而是看到了在使用这些术语中所隐藏的人的认知错误,我们追本溯源 ...
个人分类: 不确定性问题和算法讨论|4526 次阅读|3 个评论 热度 2
英语博文:NDTM的两个来源初析-NDTM的歧义性
柳渝 2017-11-25 14:43
在计算复杂性理论中,NP的形式化定义是:“NP是NDTM(NonDeterministic Turing Machine)多项式时间可接受的语言”,即“NP是NDTM多项式时间可判定解的存在的问题”。 这里我们追本溯源NP概念形成的历史,揭示NDTM指称两个本质完全不同的概念,初析NDTM的歧义性。 一,Cook定理中的NDTM NDTM用于定义NP最初出现在Cook那 ...
个人分类: 不确定性问题和算法讨论|4247 次阅读|没有评论
英语博文:解析“多项式时间可验证” - NP定义的歧义性
热度 2 柳渝 2017-11-12 18:00
概念的“相对性”是概念 认知 的最基本原理,我们再从概念的“相对性”角度 解析基于“多项式时间可验证”的NP流行定义的“歧义性”。 一,概念的相对性 概念用于指称事物,故需能界定所指事物,使之与其他已知的相关事物区分开。在此意义上,概念具有“相对性”,即 一个 概念的 定义须 相对于已知的 概念来进行 ...
个人分类: 不确定性问题和算法讨论|4805 次阅读|4 个评论 热度 2
英语博客:P vs NP - The perplexity of Nondeterminism
热度 2 柳渝 2017-8-25 05:50
最近德国波恩大学的计算机科学家Nobert Blum声称证明了“P/=NP” ,再次引发学术界对世纪难题“P vs NP”的关注与讨论。事实上,此问题不仅是计算机理论的基本问题,更与如今蓬勃发展的人工智能的基本理论问题密切相关。 “P vs NP”反应的是计算机领域最基本的“确定性问题与不确定性问题”的关系问题,然而由于流行的N ...
个人分类: 不确定性问题和算法讨论|3338 次阅读|4 个评论 热度 2

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

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

GMT+8, 2024-3-28 19:13

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部