CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

谁说P≠NP?中国人的智力要让世界震惊!

已有 3362 次阅读 2015-7-1 07:52 |个人分类:科研论文|系统分类:科研笔记| k-CNF-SAT

谁说PNP

姜咏江

   据说世界头号难题P/NP问题,最后落实到NPC问题是否是P问题上?依据斯提芬.库克的理论,又落实到3-CNF-SAT这个NPC问题是否是P问题上。直至今日,世界上尚未见到有人能够明确地指出3-CNF-SAT是否是P问题。

   本文作者经过较长时间的研究,对NPC问题k-CNF-SAT创造性地提出了消去法求解的简捷方法(见http://blog.sciencenet.cn/blog-340399-901277.html ),并指出k阶合取范式f(x1,…,xn)的子句最多数量,从而可以明确地证明k-CNF-SAT求解的时间复杂度是一个多项式时间O(nk)。这就简单地证明了P=NP

下面就是通俗简单的证明。

1.              k-CNF-SAT的子句最多有C2nk

       n个逻辑变量所成的k阶合取范式最多有多少个子句?在合取范式子句中仅可以出现变量与其非的表示。我们将逻辑变量和这个变量的非分别用xx’表示,那么n个逻辑变量所成的k阶合取范式子句数,就是从2n个元素中取出k个的组合数C2nk

例如,n=3k=2时的合取范式2-CNF-SAT子句最多有C2nk=15:

f(x1,x2,x3)= (x1+x1’) (x2+x2’) (x3+x2’) (x1+x2) (x1+x3) (x2+x3) (x1’+x2’) (x1’+x3’) (x2’+x3’) (x1’+x2) (x1’+x3) (x1+x2’) (x2’+x3) (x1+x3’) (x2+x3’).

2.              消去法求解k-CNF-SAT的时间复杂度为O(nk)

由于k-CNF-SAT子句最多有C2nk个,所以用消去法确定f(x1,…,xn)=1的解,每次操作至少消去1个子句。因而,求解过程最多操作不超过C2nk次,而C2nk=2n (2n-1)…(2n-k+1)/k!,这是一个k次多项式。于是按照所谓的算法时间复杂度的大O表示法,求解合取范式k-CNF-SATf(x1,…,xn)=1的解是一个多项式时间,即可以用O(nk)来表示。

 

友情提示:引用请注明出处(盗用必究)。Email: accsys@126.com

2015-7-1

 



http://blog.sciencenet.cn/blog-340399-901874.html

上一篇:n-CNF-SAT消去法求解
下一篇:答柳渝对消去法求解k-CNF-SAT的质疑

3 杨正瓴 陈辉 icgwang

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

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

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

GMT+8, 2021-3-8 03:11

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部