博文
k-CNF-SAT子句消去计数法求解
|||
k-CNF-SAT子句消去计数法求解(正式发表）
姜咏江
Email:accsys@126.com
摘要：给出子句消去计数法算法，该算法可以很容易求出k-CNF-SAT的全部解。证明了斯提芬.库克定义下的NPC问题就是一个P类问题。
关键词：NPC，P/NP问题，子句消去计数法
1. 背景
P/NP问题曾于2000年被美国克雷数学所定为最难的难题，有甚者说其挑战了人类智慧。2010年8 月6 日，HP LAB的 Vinay Deolalikar 教授宣布证明了P!=NP，证明文章 已经发送到该问题各相关领域专家手中，等待检验，在他的主页上，证明过程已经公布（PDF格式共103页）。
本文将给出NPC问题k-CNF-SAT就是一个P类问题的算法和相关证明，跟Vinay Deolalikar 教授唱个反调，主张P=NP，是否会得到学术界认可，有待每个感兴趣的人检验。
2. 子句消去计数法求解的算法
一个逻辑多项式如果存在一项的值是1，那么这个逻辑多项式的值一定就是1。同样，一个逻辑项的存在为0的因子，那么这个逻辑项的值一定是0。逻辑变量非的值，一定是逻辑变量值的反码。逻辑运算的这些基本规律是子句消去法计数成立的基础。
本文用“+”表示或运算，用“’”表示非运算，与运算符号省略。
我们可以利用逐次消去n个变量或其非运算一方，通过n次消去，最终确定消去的变量取值是否是合取范式值为1 的解。这叫子句消去法。用子句消去法进行改造，获得了下面的子句消去计数法。
用子句消去计数法求解k-CNF-SAT问题算法如下：
（0） 设立n元单侧计数器：x1’x2’x3’…xn-1’xn’[],x1’x2’x3’…xn-1’xn [],…, x1x2x3…xn-1xn []，共计2n个。计数器后面的方括号内放k个变量都在其中的子句数。计数器初值为0。
（1） 去掉值总为1的恒一子句，则n元k-CNF的子句最多剩有C2nk-nC2n-2k-2。
从前到后检查每个子句，并将k个变量都在某计数器中的计数器加1。这一过程显然是多项式时间。
（2） 计数后，寻找计数器为0的计数器名称，以其每个变量表示的反码取值，得到的n位二进制数就是这个k-CNF-SAT的全部解。
（3） 若没有计数器值为0，则表示此k-CNF-SAT无解。
例1，f(x1,..., x6)= (x1+x1'+x2')(x2+x3+x4)(x1'+x3'+x4')(x1'+x2+x5')(x2+x3+x6)(x1+x5+x6')，求满足
f(x1,..., x6)=1的解。
（0）设计数器x1’x2’x3’…x5’x6’[],x1’x2’x3’…x5’x6 [],…, x1x2x3…x5x6 []，共计64个。
（1）去掉恒一子句(x1+x1'+x2')，剩(x2+x3+x4)(x1'+x3'+x4')(x1'+x2+x5')(x2+x3+x6)(x1+x5+x6')
（2）剩下非恒一合取范式的第一子句使含x2x3x4标识的计数器都加1；第二子句使含x1'x3'x4'标识的计数器都加1；继续5次，查遍所有子句。
（3）令为0计数器的变量取反码值即得解。例如，计数器x1’x2’x3 x4’x5’x6 [0]，于是得f(x1,..., x6)值为1的解有：（110110）。
（4）一次性可以写出所有解。互为反码标识的计数器都为0，则对应逻辑变量组合双方都是解。
验证：
对于所得解可以带入原式验证。将x1=1、x2=1、x3=0、x4=1、x5=1、x6=0带入原式得：f(1,1,0,1,1, 0)=1。
3. 概念与性质
为什么子句消去计数法就能够求出k-CNF=1的解？它的证明就在下面的概念和方法中。
定义1：如果子句中同时有逻辑变量和其反表示，则称子句为恒一子句。
显然，恒一子句的值总是1，与逻辑变量的取值无关。
定义2：所有包含变量x的非恒一子句叫x相关子句。
定义3：我们将n对互反变量只取变量或变量非，得到的n个变量组合，叫一侧。显然，n个变量的一侧有2n个。
子句消去计数法的计数器就是记录一侧含有的子句数量的。
定理1：n个变量合取范式k-CNF中一侧相关子句数最多为Cnk。
证明：因为一侧只有n个变量，从中取出k个为Cnk。
此定理可以用来检查给定的合取范式是否不正确。如果给出的合取范式的一侧相关子句超过这个数，则可判定合取范式有错误。
定义4：将合取范式一个变量的值定为1的子句消去求解的方法，称为子句消去法。
显然，子句消去法经过n次消去，若没有剩余子句，则k-CNF是可满足的，反之不满足。
定理2：非恒一子句全体，消去x相关子句中，一定不含有其反变量x’。
证明：因为非恒一子句x与x’是不同时出现在一个子句，所以消去x相关子句，x’相关子句依然存在。
完全定理：n个逻辑变量所成的k元合取范式k-CNF，最多有C2nk个子句。非恒一子句最多有C2nk-nC2n-2k-2个。
证明：因为每个子句的元素可以是逻辑变量或它的非，这相当从2n个元素中取出k个的组合数，即为C2nk。而恒一子句最多有nC2n-2k-2个，所以非恒一子句最多有C2nk-nC2n-2k-2个。
推论：完全合取范式的值恒为0。
因为完全合取范式包含x与x’的所有相关子句。所以用子句消去法无论经过怎样的n次消去子句，都不能使剩余没有子句。
可满足定理：若非恒一子句中互反变量有一侧相关子句不存在，则k-CNF-SAT可满足。
证明：因为x的相关子句全体包含一侧所有的n个变量或其非，如果一侧不存在，则可确定其相反一侧变量逐一消去，依据定理2可知最终没有剩余子句。
满足定理是我们进行k-CNF-SAT求解子句消去计数算法正确性的依据。
步数定理：用子句消去计数法确定k-CNF可满足全部解，最多用了C2nk次检查。
因为子句数不超过C2nk,得证。
步数定理告诉我们，上面介绍的求解算法是一个多项式时间算法。
4. 结论
一般P/NP问题的描述与斯提芬.库克的NP、NPC定义有不同之处。本文仅是站在伟大的库克的肩膀上，用子句消去计数法原理，找出了k-CNF-SAT问题解的算法。
斯提芬.库克一脉学术观点认为：若任意NPC问题可证明是P问题，那么P=NP成立。本文给出了k-CNF-SAT问题一侧相关计数求解算法，是典型所谓的“多项式时间”，故可以得出在斯提芬.库克定义的条件下，可以有NPC＝P，这个结论否定了P！=NP。
请看：http://blog.sciencenet.cn/blog-340399-928224.html
（本论文系首创，引用请注明出处）
2015-7-16
https://blog.sciencenet.cn/blog-340399-905817.html
上一篇：我若发表K-CNF-SAT多项式时间求出全部解方法，谁敢给我做评判？
下一篇：杜立智希望你再批评一下我的初等数学水平！
