k-CNF-SAT 无解条件 姜咏江 K 阶合取范式如何去判断有无解有实际意义。判断无解的方法简单，只要某子句的变量完全表示都存在，那么合取范式必定无解。什么叫子句的完全表示？ 举例来说， k=3 ，那么子句的完全表示有 2 3 =8 个： x i ’+x j ’+x m ’ ， x i ’+x j ’+x m ， x i ’+x j +x m ’ ， x i ’+x j +x m ， x i +x j ’+x m ’ ， x i +x j ’+x m ， x i +x j +x m ’ ， x i +x j +x m 。 容易看出这就是 3 位二进制的 8 个数。 一般化，只要 k 个变量的各自正反表示子句都存在，则 k-CNF-SAT 必定无解。其原理来自子句子句消去记数法分组求解（见 http://blog.sciencenet.cn/blog-340399-928224.html ） 给子句完全表示下一个定义。 定义 ： k 个逻辑变量表示子句对应的 k 位二进制数都存在，则称这些子句为子句完全表示。 由于子句完全表示的每个子句与 k 位二进制数一一对应，因而通过子句消去法总会有子句剩余下来，故这 k 个变量给定任何值都不会使合取范式有解。 为了能够快速判断 k-CNF-SAT 是否有解，在子句输入的过程中，要将能够构成子句完全表示的成员放到一起，如果有一组完全表示存在，则不必费力气求解了。 转： http://blog.sciencenet.cn/blog-340399-928224.html 2015-7-30
Solution k-CNF-SAT by The Remove Clause Counting Method Jiang Yongjiang Email: accsys@126.com Abstract : This paper presents a method for the remove clauses, which can be easily obtained from the total solution of k-CNF-SAT. This paper can prove NPC =P. Keywords : NPC, P/NP problem, Count clause removed 1. The Count Clause Removed Algorithm In this paper, we use the logical connectives are + (or),’ (not), and the (and) connective is omitted. We now give the following special algorithm of Count clause removed. (0) The establishment for n variables of one side symbols counter. like this x 1 ’x 2 ’x 3 ’…x n-1 ’ x n ’ ,…, x 1 x 2 x 3 …x n-1 x n plus 1. (2) Final we can find which counter is 0, then the name symbol is x i ,then x i =0. if is x i ’,then x i =1.So we can get all solutions of the k-CNF-SAT. (3) If non any counter is 0, the k-CNF cannot be equal to 1. Example : f ( x 1 ,..., x 6 )= ( 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 '),please find out the satisfiable solutions. Solution: (0) The counters are x 1 ’x 2 ’x 3 ’…x 5 ’x 6 ’ ,…, x 1 x 2 x 3 …x 5 x 6 , ( x 1 '+ x 3 '+ x 4 ') can be plus 1 in counters x 1 ’ …x 3 ’ x 4 ’… ,…, etc. (2) Check all of the clause and then look at the counters.If a counter’s value is 0, the oppsite counter’s name is the solution. For instance,the counter x 1 ’x 2 ’x 3 x 4 ’x 5 ’x 6 value is 0,then we have f (1,1,0,1,1, 0)=1. 2. Concepts and Properties Way can we get all the solutions of the k-CNF=1 by the Count clause removed algorithm ? Definition 1: if a clause has x and x’, then the clause is called a one-clause. Definition 2: If a clause has x and is not one-clause,then it is called x-clause. Definition 3: If we only have x or only have x’ the n variables word is called a One-side. We can know there is 2 n One-side. The counters are to record the number of clauses that are contained in One-side. Theorem 1: One-side of n variables in k-CNF for the highest number of related clauses is . Proof: becauseOne-side only have n variables, so get k ≤ n is . Thus we know the counter’s maximum value is . Definition 4: Remove clause ,that the one variable value is 1,it is called clause remove method in k-CNF. Obviously,clause remove n times if there is not any remain clause,The k-CNF=1, otherwise it will be 0. Theorem 2 ： k-CNF, there is not any One-clause,if remove x-clause connot remove x’-clause. Proof: Because there is not any One-clause,so if we remove x-clause then we connot remove x’-clause. Theorem 3 ： n variables k-CNF most have clauses, and One-clause maximum is . Definition 4: have clauses k-CNF is calld complete k-CNF. Corollary : Complete k-CNF value of constant is 0. Theorem 4 ： Any One-clause is not in k-CNF and if one One-side is not there ,then the k-CNF=1. Proof : The x-clause contains all of the variables on one-side. If the one-side does not exist, it is determined that the opposite one-side remove thus there will not be any residual clause. 3. Conclusion The Count clause removed algorithm is easy and simple method to the k-CNF-SAT. It is in polynomial time problem solving the k-CNF-SAT problem,so we can conclude NPC=P. Original paper: http://blog.sciencenet.cn/blog-340399-905817.html 2015-7-17
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
谁说 P ≠ NP ？ 姜咏江 据说世界头号难题 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 ( x 1 ,…, x n ) 的子句最多数量，从而可以明确地证明 k-CNF-SAT 求解的时间复杂度是一个多项式时间 O( n k ) 。这就简单地证明了 P=NP ！ 下面就是通俗简单的证明。 1. k-CNF-SAT的 子句最多有 C 2n k 个 n 个逻辑变量所成的 k 阶合取范式最多有多少个子句？在合取范式子句中仅可以出现变量与其非的表示。我们将逻辑变量和这个变量的非分别用 x 与 x’ 表示，那么 n 个逻辑变量所成的 k 阶合取范式子句数，就是从 2n 个元素中取出 k 个的组合数 C 2 n k 。 例如， n=3 ， k=2 时的合取范式 2-CNF-SAT 子句最多有 C 2 n k =15: f ( x 1 , x 2 , x 3 )= ( x 1 + x 1 ’) ( x 2 + x 2 ’) ( x 3 + x 2 ’) ( x 1 + x 2 ) ( x 1 + x 3 ) ( x 2 + x 3 ) ( x 1 ’+ x 2 ’) ( x 1 ’+ x 3 ’) ( x 2 ’+ x 3 ’) ( x 1 ’+ x 2 ) ( x 1 ’+ x 3 ) ( x 1 + x 2 ’) ( x 2 ’+ x 3 ) ( x 1 + x 3 ’) ( x 2 + x 3 ’). 2. 消去法求解 k-CNF-SAT 的时间复杂度为 O( n k ) 由于 k-CNF-SAT 子句最多有 C 2n k 个，所以用消去法确定 f ( x 1 ,…, x n )=1 的解，每次操作至少消去 1 个子句。因而，求解过程最多操作不超过 C 2n k 次，而 C 2n k =2n (2n-1)…(2n-k+1)/k!，这 是一个 k 次多项式。于是按照所谓的算法时间复杂度的大 O 表示法，求解合取范式 k-CNF-SAT 的 f ( x 1 ,…, x n )=1 的解是一个多项式时间，即可以用 O( n k ) 来表示。 友情提示：引用请注明出处（盗用必究）。Email: accsys@126.com 2015-7-1
标签: k-CNF-SAT
