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

博文

对NP的误导和对NP的误解

已有 2530 次阅读 2015-7-1 21:30 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| 消元法

“P versus NP”成为世纪难题原因复杂。在理论上,专业学者混淆了P和NP的层次,将NP定义为“Non-deterministic Polynomial time,不确定性多项式时间)”,导致NP的本质“不确定性”的消失,此误导可追溯到Cook定理。

而一般对“P versus NP”感兴趣的大众学者,由于缺乏对NP与P的形式化定义的深入了解,往往以数学中的常见问题(P问题)来理解NP,也就完全误解了NP与P的关系,比如,网友姜咏江的博文:“谁说P≠NP?中国人的智力要让世界震惊!(http://blog.sciencenet.cn/blog-340399-901874.html)”,“k-CNF-SAT消去法求解(http://blog.sciencenet.cn/blog-340399-901277.html)”等中所述,就具有代表性。这里就网友姜咏江的结论“求解合取范式k-CNF-SAT的f(x1,…,xn)=1的解是一个多项式时间,即可以用O(n^k)来表示”,集中性地分析一下,为什么我们认为是错误的:

1,首先需理解“求解合取范式k-CNF-SAT”所指,是说:任给一个k-CNF:f(x1,..., xn),判定f(x1,..., xn)是可满足的,还是不可满足的,这与网友姜咏江的“k-CNF-SAT消去法求解”具有完全不同的性质数学的联立方程组表达的是“变量数值之间”的相互约束,因此可以采用消元法,最终得到n个变量賦值组成的确定的解;而k-CNF-SAT合取范式表达的是“变量之间的关系”的相互约束(专业术语:约束满足问题 Constraint Satisfaction Problem CSP),只能用搜索的方法求解

2,n个变量共有指数个賦值关系:2^n 。这2^n个赋值构成2SAT关系时,是“多项式时间复杂度”;这2^n个赋值构成3SAT关系时,是“指数时间复杂度”(“算法复杂度”的意义以后另行解释)。

指数时间复杂度问题只能搜索求解,而对这样的问题是否存在着多项式时间复杂度的算法涉及到“判定问题”的本质,不可由某些具体的例子推导P=NP或P≠NP的“完全性”结论,这也正是“P versus NP” 成为世纪难题的一个原因,这里涉及到的认知层次的问题,我们在博客中己反复讨论过了。

与此相似的误解还有其它形式,但错误性质基本相同,而且一旦形成这种错误观念,很难自拔,也难与争辩,往往要经过很长时期的反复理解才能“顿悟”,以后我们还会结合一些其他的例子适当解释,但我们目前的主要工作还是在对NP误导的理论层面进行分析,以前的博文“关于NP讨论中的论域问题(http://blog.sciencenet.cn/blog-2322490-890199.html)”中我们提出NP讨论中的论域问题,也是为了在理论分析中避免发生概念内涵的分岐,而且这也是产生P与NP关系混淆和混乱的认识方面的基本原因,因此借此机会我们再次提醒大家,注意讨论中的范畴、范式、概念内涵的一致性,避免“表面上争论是同一个问题,实际上各说各自不同的事情”这样的情况。




http://blog.sciencenet.cn/blog-2322490-902088.html

上一篇:法国高中哲学课程
下一篇:法国高考“法语”笔试(理科,经济社会科,2014年)

5 杨正瓴 姜咏江 罗德海 陈辉 icgwang

该博文允许注册用户评论 请点击登录 评论 (10 个评论)

数据加载中...
扫一扫,分享此博文

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

GMT+8, 2021-12-1 09:34

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部