科学网

 找回密码
  注册
“不确定性问题(NP)”案例分析 - HCP与CP
柳渝 2017-2-13 21:40
众所周知,判断哈密尔顿回路的存在是一个NP问题,而判断普通回路的存在却是一个P问题。我们对比分析这二个问题,帮助直觉体会NP的本质属性,揭示“多项式时间可验证”的流行NP定义所隐藏的认知错误。 一,Cycle Problem(CP)与Hamiltonian Cycle Problem(HCP) 设G=(V,E)是无向图,V是结点的集合,E是边的集合,记结点 ...
个人分类: 不确定性问题和算法讨论|5033 次阅读|没有评论
从集合论的观点看NP
热度 2 柳渝 2017-1-28 13:04
Cook在介绍千禧年难题“The P versus NP Problem”[1]时说: -The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time. 这就是NP完备理论中P和NP的形式化定义:P ...
个人分类: 不确定性问题和算法讨论|4941 次阅读|6 个评论 热度 2
智能制造:困惑、困难和希望
热度 2 柳渝 2017-1-12 12:24
“数字化企业网(http://articles.e-works.net.cn/it_overview/article132816.htm)”刋出我们的《智能制造:困惑、困难和希望》。 如我们所说:传统制造业向智能制造的转型远不是制造业份内的事,也不是“赶、超世界先进水平”、“后发优势”、“补短板”、“全民创新”等口号所能简单概括的,对当前基本形势认知上的肤 ...
个人分类: 不确定性问题和算法讨论|3514 次阅读|3 个评论 热度 2
“个人云”文化:2017“个人云”(办公)实用方法
柳渝 2017-1-10 22:00
《金融博览》2017第一期刋出及“数字化企业网( http://articles.e-works.net.cn/cloud/article132991.htm )”转载了我们的《“个人云”文化》,此文阐述通过个人化途径把“文化”这个极为广泛的概念扩展到虚拟空间(CyberSpace),这只是最初步的探索,后面有着极为复杂的层次和广泛而深刻的相关性,比如,现实世界中的 ...
个人分类: 不确定性问题和算法讨论|3220 次阅读|没有评论
解读NDTM的概念偷换-Sipser书中NP二个定义等价的证明
热度 3 柳渝 2017-1-3 05:53
在计算复杂性理论中,NP是基于“不确定性图灵机(nondeterministic Turing machine,NDTM)”来定义的,指NP是NDTM多项式时间可求解的问题。于“求解”的定义,又可表达为基于“判定”的定义,指NP是NDTM多项式时间可接受的语言(即NDTM多项式时间可判定解的存在),此定义源于Cook定理,其中的NDTM具有“神喻机(Orac ...
个人分类: 不确定性问题和算法讨论|4250 次阅读|8 个评论 热度 3
认知云里说NP
热度 4 柳渝 2016-12-22 12:56
我们的NP理论是建立在可计算性理论基础上的,在算法理论、逻辑和理论扩展上(如人工智能和智能哲学)是一致的,但在与同行、网友、群友和爱好者的交流中,最纠缠的还是认知层面上的问题,集中在这样一个提问:现有理论中的NP(NDTM)的概念是简单清楚的,而你们的NP(Nondeterministic Problem)与此完全不同,为什么要 ...
个人分类: 不确定性问题和算法讨论|3285 次阅读|17 个评论 热度 4
再谈为什么质疑NP的“可验证定义”
热度 5 柳渝 2016-12-5 20:45
这里回应网友李红雨的博文( http://blog.sciencenet.cn/home.php?mod=spaceuid=46717do=blogquickforward=1id=1018695 ),总结性的再谈我们为什么质疑 “NP是多项式复杂度的算法可验证的问题” 这一定义。 首先应注意到, 我们的讨论首重解读 流行的NP定义,其 目的是 辨析这些 定义 是否 捕捉到 ...
个人分类: 不确定性问题和算法讨论|5059 次阅读|15 个评论 热度 5
不确定性问题(NP)与“不确定性”- 基本定义的一个简要解释
热度 6 柳渝 2016-11-28 13:23
李红雨等诸网友的提问集中在我们将NP定义为“不确定性问题”上。李红雨实际上是在问:“不确定性”有很多意义,我们为何能统一为NP这个概念?所以这是在认知意义上提问:自然语言中的“不确定性”究竟指什么? 自然语言中的“不确定性”确实有各种不同的意义,这才会有李红雨提到的不同层次上的“不确定性”问题,也就是 ...
个人分类: 不确定性问题和算法讨论|8428 次阅读|11 个评论 热度 6
司汤达不解“负负得正”的故事-概念认知
柳渝 2016-10-19 05:33
从形式语言与自然语言关系的角度,博文( http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogid=1008367 )对“负债× 负债=收入 ”的常识性错误进行了分析,这里我们再从思维的角度对此分析,借此对“思维”这个基本概念作初步的讨论。 一,“负负得正”故事的主题 司汤达的老师给司汤达讲了“ ...
个人分类: 不确定性问题和算法讨论|4179 次阅读|没有评论
司汤达不解“负负得正”的故事-形式语言与自然语言
柳渝 2016-10-13 04:53
撰写小说《红与黑》的法国著名作家司汤达(Stendhal,1783-1842)在他的自传小说《亨利·勃吕拉传》中,叙述了因没有人能跟他解释负负为何得正而让他对数学失望的往事,故事虽短却意味深长,实际上揭示了西方学术思想和理论中形式语言与自然语言纠缠,这一最令人困惑的现象。 一,司汤达不解“负负得正” 司汤达说,“ ...
个人分类: 不确定性问题和算法讨论|7739 次阅读|没有评论

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

GMT+8, 2024-3-28 17:47

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部