k-CNF-SAT 子句消去计数法求解(正式发表） 姜咏江 Email:accsys@126.com 摘要 ：给出子句消去计数法算法，该算法可以很容易求出 k-CNF-SAT 的全部解。证明了斯提芬 . 库克定义下的 NP C 问题 就是一个 P 类问题。 关键词 ： NPC ， P/NP 问题，子句消去计数法 1. 背景 P/NP 问题曾于 2000 年被美国克雷数学所定为最难的难题，有甚者说其挑战了人类智慧。 2010 年 8 月 6 日， HP LAB 的 Vinay Deolalikar 教授宣布证明了 P!=NP ，证明文章 已经发送到该问题各相关领域专家手中，等待检验，在他的主页上，证明过程已经公布（ PDF 格式共 103 页）。 本文将给出 NP C 问题 k-CNF-SAT 就是一个 P 类问题的算法和相关证明，跟 Vinay Deolalikar 教授唱个反调，主张 P=NP ，是否会得到学术界认可，有待每个感兴趣的人检验。 2. 子句消 去 计数 法求解的算法 一个逻辑多项式如果存在一项的值是 1 ，那么这个逻辑多项式的值一定就是 1 。同样，一个逻辑项的存在为 0 的因子，那么这个逻辑项的值一定是 0 。逻辑变量非的值，一定是逻辑变量值的反码。逻辑运算的这些基本规律是子句消去法计数成立的基础。 本文用“ + ”表示或运算，用“ ’ ”表示非运算，与运算符号省略。 我们可以利用逐次消去 n 个变量或其非运算一方，通过 n 次消去，最终确定消去的变量取值是否是合取范式值为 1 的解。这叫子句消去法。用子句消去法进行改造，获得了下面的 子句消去计数法 。 用子句消去计数法求解 k-CNF-SAT 问题算法如下： （0） 设立 n 元单侧计数器： x 1 ’x 2 ’x 3 ’…x n-1 ’ x n ’ ,…, x 1 x 2 x 3 …x n-1 x n ,x 1 ’x 2 ’x 3 ’…x 5 ’x 6 ，共计 64 个。 （ 1 ）去掉恒一子句 ( x 1 + x 1 '+ x 2 ') ，剩 ( x 2 + x 3 + x 4 )( x 1 '+ x 3 '+ x 4 ')( x 1 '+ x 2 + x 5 ')( x 2 + x 3 + x 6 )( x 1 + x 5 + x 6 ') （ 2 ）剩下非恒一合取范式的第一子句使含 x 2 x 3 x 4 标识的计数器都加 1 ；第二子句使含 x 1 ' x 3 ' x 4 ' 标识的计数器都加 1 ；继续 5 次，查遍所有子句。 （ 3 ）令为 0 计数器的变量取反码值即得解。例如，计数器 x 1 ’x 2 ’x 3 x 4 ’x 5 ’x 6 ，于是得 f ( x 1 ,..., x 6 ) 值为 1 的解有：（ 110110 ）。 （ 4 ）一次性可以写出所有解。互为反码标识的计数器都为 0 ，则对应逻辑变量组合双方都是解。 验证 ： 对于所得解可以带入原式验证。将 x 1 =1 、 x 2 =1 、 x 3 =0 、 x 4 =1 、 x 5 =1 、 x 6 =0 带入原式得： f (1,1,0,1,1, 0)=1 。 3. 概念与性质 为什么子句消去计数法就能够求出 k-CNF=1 的解？它的证明就在下面的概念和方法中。 定义 1 ：如果子句中同时有逻辑变量和其反表示，则称子句为恒一子句。 显然，恒一子句的值总是 1 ，与逻辑变量的取值无关。 定义 2 ：所有包含变量 x 的非恒一子句叫 x 相关子句。 定义 3 ：我们将 n 对互反变量只取变量或变量非，得到的 n 个变量组合，叫一侧。显然， n 个变量的一侧有 2 n 个。 子句消去计数法的计数器就是记录一侧含有的子句数量的。 定理1 ： n 个变量合取范式 k-CNF 中一侧 相关子句数最多为C n k。 证明 ：因为一侧只有 n 个变量，从中取出 k 个为 C n k 。 此定理可以用来检查给定的合取范式是否不正确。如果给出的合取范式的一侧相关子句超过这个数，则可判定合取范式有错误。 定义 4 ：将合取范式一个变量的值定为 1 的子句消去求解的方法，称为子句消去法。 显然，子句消去法经过 n 次消去，若没有剩余子句，则 k-CNF 是可满足的，反之不满足。 定理2 ：非恒一子句全体，消去 x 相关子句中，一定不含有其反变量 x’ 。 证明 ：因为非恒一子句 x 与 x’ 是不同时出现在一个子句，所以消去 x 相关子句， x’ 相关子句依然存在。 完全定理 ： n 个逻辑变量所成的 k 元合取范式 k-CNF ，最多有C 2n k 个子句。非恒一子句最多有 C 2n k - n C 2n-2 k -2 个。 证明 ：因为每个子句的元素可以是逻辑变量或它的非，这相当从 2n 个元素中取出 k 个的组合数，即为C 2n k 。而恒一子句最多有 n C 2n-2 k -2 个，所以非恒一子句最多有 C 2n k - n C 2n-2 k -2 个。 推论 ：完全合取范式的值恒为 0 。 因为完全合取范式包含 x 与 x’ 的所有相关子句。所以用子句消去法无论经过怎样的 n 次消去子句，都不能使剩余没有子句。 可满足定理 ：若非恒一子句中互反变量有一侧相关子句不存在，则 k-CNF-SAT 可满足 。 证明 ：因为 x 的相关子句全体包含一侧所有的 n 个变量或其非，如果 一侧不存在，则可确定其相反一侧变量逐一消去，依据定理 2 可知最终没有剩余子句。 满足定理是我们进行 k-CNF-SAT 求解子句消去计数算法正确性的依据。 步数定理 ：用子句消去计数法确定 k-CNF 可满足全部解，最多用了 C 2n k 次检查。 因为子句数不超过 C 2n k ,得证。 步数定理告诉我们，上面介绍的求解算法是一个多项式时间算法。 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
标签: 子句消去计数法
