3-sat剩余子句块多解表示方法 姜咏江 使用子句消去法对 3-SAT 求解，最后会碰到剩余子句块多解的情况。如果我们只选择 0 和 1 表示，就会使那些很容易就得到的多解无法表出，为此需要引进 确定了一个变量值后 的剩余多解子句块的表示方法，这样一次可以获得更多的 3SAT 解表示。下面表 1 和表 2 中的 $ 表示该变量值已经确定，上面一行是表示符号。 表 1 剩余一个子句 表示： v v t t k k q q 变量： X i X j X k X i X j X k X i X j X k X i X j X k 剩值： $ 0 0 $ 1 1 $ 1 0 $ 0 1 vv 表示 x j x k 的值是 0* 或 *0, tt 表示 x j x k 的值是 1* 或 *1, kk 表示 x j x k 的值是 1* 或 *0, qq 表示 x j x k 的值是 0* 或 *1 。“ * ”表示 0 或 1 。 表 2 剩余 2 个子句 表示： 2 2 3 3 2 2 3 3 变量： X i X j X k X i X j X k X i X j X k X i X j X k 剩值： $ 0 0 $ 1 0 $ 1 1 $ 0 1 1 1 0 1 0 0 1 0 22 表示 x j x k 的值是 01 或 10, 33 表示 x j x k 的值是 11 或 00 。 这种表示一般只用于剩余的独立子句块，如若是多解的关联段，尚需设定值求解，到最后碰到此种情况方可使用。 需要说明，子句消去法并不能够一次性求出 3SAT 的全部解，除非 3SAT 只有唯一解和只有我们这里给出的表示法能够表出的那些解。这种多解表示法只是对剩余多解子句块运用的一种表示法，目的是在 3SAT 的一次求解中能够尽可能地表示出更多的解。 剩余只有 3 种子句的子句块一定有唯一解。剩余有 4 种类型子句的子句块一定无解。 2015-12-15
为什么子句分段消去法可以求出 3SAT 的解？ 姜咏江 A proof that P = NP could havestunning practical consequences, if the proof leads to efficient methods forsolving some of the important problems in NP . 上面这句话引自维基百科的 P versus NP 。说得是否有些过分了？ 用子句分段消去法求解 3-CNF=1 的解，首先是将逻辑变量表达的问题结构化了，这种 3-CNF 特有的结构是求解的基础。子句间形成的子句块制约了子句中逻辑变量的自由变化，使 3-CNF=1 的解转化成了局部的“子句块解”和“关联段解”，从而避开了处处要从全局变量变化来确定逻辑变量值的传统方法。 子句块中子句数量的变化，为我们揭示了变量取值的规律，而关联段求解中产生的动态块，又为我们指明了段中变量值变化的规律和相互制约关系。所以我们才能够依据这些 3-CNF 中变量变化的内在规律，找到求解 3-SAT 问题满足解的方法。这是一种函数关系的体现， 不客气地说，我是计算机科学理论方法的里手，仔细研究，这个 P/NP 问题应该是纯数学的问题，它与计算机程序运行的时间计算等关系并不十分紧密，将其说成是计算机运行时间的问题不够贴切，因为计算机程序运行时间只与指令重复执行次数相关。 2015-10-16
库克定义下的 k-CNF-SAT ＝ P 证明（中文版） 姜咏江 Email:accsys@126.com 摘要 ：采用子句消去法证明了斯提芬 . 库克定义下的 NP C 问题 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 页）。 本文将给出 NP C 问题 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 1 , x 2 , x 3 )= ( x 1 '+ x 2 )( x 2 ’+ x 3 ’)( x 2 + x 3 ) ( x 2 ’+ x 3 ) ( x 2 + x 1 ) 。 （ 1 ）由 x 1 ' 令 x 1 =0 ，消去含有 x 1 ' 子句，剩 ( x 2 ’+ x 3 ’)( x 2 + x 3 ) ( x 2 ’+ x 3 ) ( x 2 + x 1 ) ； （ 2 ）由 x 2 ' 令 x 2 =0 ，消去含有 x 2 ' 子句，剩 ( x 2 + x 3 ) ( x 2 + x 1 ) ； （ 3 ）由 x 3 令 x 3 =1 ，消去含有 x 3 子句，剩 ( x 2 + x 1 ) 。 由于此剩余子句的值为 0 ，故 f (0,0,1)=0 。 例2 ， 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 ') ，求满足 f ( x 1 ,..., x 6 )=1 的解。 （ 1 ）令 x 1 =1 ，剩 ( x 2 + x 3 + x 4 )( x 1 '+ x 3 '+ x 4 ')( x 1 '+ x 2 + x 5 ')( x 2 + x 3 + x 6 ) （ 2 ）令 x 2 =1 ，剩 ( x 1 '+ x 3 '+ x 4 ') （ 3 ）令 x 3 =0 ，则消去值为 1 子句后，无有剩余子句。 于是得 f ( x 1 ,..., x 6 ) 值为 1 的解有：（ ***011 ），其中 * 表示为 0 或 1 不限。 验证 ： 对于所得解可以带入原式验证。将 x 1 =1 、 x 2 =1 、 x 3 =0 带入原式得： f (1,1,0, x 4 ,..., x 6 )=1 。 3. 概念与性质 定义 1 ： n 个逻辑变量全部可取 k 元子句组成的合取范式叫完全合取范式。 定义 2 ：元素对应取反的两个子句称为互反子句。 例如 3-CNF 中有子句 x 2 ’+ x 5 ’+ x 9 和 x 2 + x 5 + x 9 ’ ，它们的表示相反，因而是互反子句。 定义 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
标签: 子句消去法
