库克定义下的k-CNF-SAT＝P证明（中文版）

姜咏江

                                                Email:accsys@126.com

摘要：采用子句消去法证明了斯提芬.库克定义下的NPC问题k-CNF-SAT可以是一个P类问题。给出了子句消去法的算法。同时也给出了可以在有限步骤内求出k-CNF-SAT问题的解或指出其不满足的条件。

关键词：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。逻辑变量非的值，一定是逻辑变量值的反码。逻辑运算的这些基本规律是子句消去法成立的基础。

本文用“+”表示或运算，用“’”表示非运算，与运算符号省略。

对于k-CNF-SAT问题用子句消去法求解的算法如下：

（1）       在合取范式中取第一个子句的一个变量表示（选择过的变量x，不选x’，或选过x’则x不选），若是变量本身，定其值为1，若是变量非表示，设定变量的值为0。

（2）       消去所有含有选择变量表达形式的子句，得到剩余子句。

（3）       若还有剩余子句且有变量未选择，则转到（1）对剩余合取范式继续执行操作。

（4）       若所有变量皆选过，尚有剩余子句，则表示这不是合取范式此值为1的解；不然将前面取值按照变量顺序排好，未取值的变量表示值可以任意（用“*”代替）。

例1，f(x₁, x₂, x₃)= (x₁'+x₂)(x₂’+x₃’)(x₂+x₃) (x₂’+x₃) (x₂+x₁)。

（1）由x₁'令x₁=0，消去含有x₁'子句，剩(x₂’+x₃’)(x₂+x₃) (x₂’+x₃) (x₂+x₁)；

（2）由x₂'令x₂=0，消去含有x₂'子句，剩(x₂+x₃) (x₂+x₁)；

（3）由x₃令x₃=1，消去含有x₃子句，剩(x₂+x₁)。

由于此剩余子句的值为0，故f(0,0,1)=0。

例2，f(x₁,..., x₆)= (x₁+x₁'+x₂')(x₂+x₃+x₄)(x₁'+x₃'+x₄')(x₁'+x₂+x₅')(x₂+x₃+x₆)(x₁+x₅+x₆')，求满足

f(x₁,..., x₆)=1的解。

（1）令x₁=1，剩(x₂+x₃+x₄)(x₁'+x₃'+x₄')(x₁'+x₂+x₅')(x₂+x₃+x₆)

（2）令x₂=1，剩 (x₁'+x₃'+x₄')

（3）令x₃=0，则消去值为1子句后，无有剩余子句。

于是得f(x₁,..., x₆)值为1的解有：（***011），其中*表示为0或1不限。

验证：

对于所得解可以带入原式验证。将x₁=1、x₂=1、x₃=0带入原式得：f(1,1,0, x₄,..., x₆)=1。

3.              概念与性质

定义1：n个逻辑变量全部可取k元子句组成的合取范式叫完全合取范式。

定义2：元素对应取反的两个子句称为互反子句。

例如3-CNF中有子句x₂’+x₅’+x₉和x₂+x₅+x₉’，它们的表示相反，因而是互反子句。

定义3：如果子句中同时有逻辑变量和其反表示，则称子句为恒一子句。

显然，恒一子句的值总是1，与逻辑变量的取值无关。

性质1：合取范式去掉恒一子句，所得合取范式与原合取范式值满足性相同。

完全定理：n个逻辑变量所成的k元合取范式k-CNF，最多有C_2n^k个子句。

证明：因为每个子句的元素可以是逻辑变量或它的非，这相当从2n个元素取出k个的组合数，即为C_2n^k。

推论1：完全合取范式去除恒一子句，都是互反子句。

证明：根据完全合取范式的定义，去掉恒一子句后，如果某子句的互反子句不在其中，则知这不是完全合取范式。则知必都有互反子句。

可满足定理：子句消去法最终无剩余子句，则此合取范式是可满足的。

证明：因为子句消去的条件是值为1，若最终子句全消去，则知原合取范式是可满足的。

步数定理：用子句消去法确定了k-CNF可满足，最多用了n次化简。

此定理从子句消去法定义立得。

4.              3-CNF-SAT子句数

3-CNF的恒1子句共有：n×2(n-1)=2n(n-1)

完全3-CNF全部子句数：2n(2n-1)(2n-2)/6=2n(n-1)(2n-1)/3                                      

完全3-CNF去掉恒一子句的可能子句数：2n(n-1)(2n-1)/3-2n(n-1)=2n(n-1) (2n-4)/3

5.              结论

一般P/NP问题的描述与斯提芬.库克的NP、NPC定义有不同之处。本文仅是站在伟大的库克的肩膀上，找出了特出k-CNF-SAT问题不满足的条件，并推出子句消去法求k-CNF-SAT问题满足解的一种方法。

斯提芬.库克一脉学术观点认为：若任意NPC问题可证明是P问题，那么P=NP成立。本文给出了k-CNF-SAT问题的n次化简求解法，并且对于n位二进制数是否是n元逻辑变量的k-CNF-SAT解的验证，也肯定了是典型所谓的“多项式时间”，故可以得出在斯提芬.库克定义的条件下，可以有NPC＝P，这个结论否定了P！=NP。

2015-7-4