博文
答柳渝对消去法求解k-CNF-SAT的质疑
|||
答柳渝对消去法求解k-CNF-SAT的质疑
姜咏江
数学和计算机本身都是实实在在的东西，一定要在肯定概念的前提下来讨论问题。下面这段话是从Introduction To Algorithms第三版的中文译本抄录下来的，不知你是否认可？
就以我在博文中所举例的逻辑函数为例：
f(x1,x2,x3) = (x1+x1’) (x2+x2’) (x3+x2’) (x1+x2) (x1+x3) (x2+x3) (x1’+x2’) (x1’+x3’) (x2’+x3’) (x1’+x2) (x1’+x3) (x1+x2’) (x2’+x3) (x1+x3’) (x2+x3’).
这个函数是不会有f(x1,x2,x3) = 1的解。由变量的对称性，可知有两个变量的子句只要我们用消去因子法，分别设定00，01，11，这三个值，就可以断定2-CNF是否是可以满足，而无需考察更多。如果k-CNF的k=5，那么只需考察00000，00001，00011，00111，01111，11111这些值就知道了。
注意，由对称性可知，k-CNF-SAT问题无需考察n元0或1的向量，只需考察k元即可（k≤n）。考察总数不会超过k+1，而不用考察2n个n元0或1 的向量。
下面的消去法求解可以告诉我们结果（不是高斯消去法）。
x1=1, 得(x2+x2’) (x3+x2’) (x2+x3) (x1’+x2’) (x1’+x3’) (x2’+x3’) (x1’+x2) (x1’+x3) (x2’+x3) (x2+x3’).
x2=1, 再得(x3+x2’) (x1’+x2’) (x1’+x3’) (x2’+x3’) (x1’+x3) (x2’+x3) =0
x1=0, 得(x2+x2’) (x3+x2’) (x1+x2) (x1+x3) (x2+x3) (x2’+x3’) (x1+x2’) (x2’+x3) (x1+x3’) (x2+x3’).
x2=0,再得(x1+x2) (x1+x3) (x2+x3) (x1+x3’) (x2+x3’) =0
x1=0, 得(x2+x2’) (x3+x2’) (x1+x2) (x1+x3) (x2+x3) (x2’+x3’) (x1+x2’) (x2’+x3) (x1+x3’) (x2+x3’).
x2=1, 再得(x3+x2’) (x1+x3) (x2’+x3’) (x1+x2’) (x2’+x3) (x1+x3’) =0
从蓝颜色子句可见原式无满足解。
象本例这种k-CNF表达式，被我称为“完全k-CNF”表达式，而k-CNF表达式子句的数量不到C2nk个，我们称为非完全k-CNF表达式。完全k-CNF是不会有解满足f(x1,x2,…,xn) = 1的。只有“残缺的”k-CNF表达式k元解向量才有可能使f(x1,x2,…,xn) = 1。
再与你简单谈谈实际如何更快地验证一个k位二进制表示的数会不会是k-CNF-SAT的解吧。依据逻辑表达式消去法原理，做起来非常简单。我们就用一个k=3元子句为例说明一下。
假设我们要检查x1=1，x2=0，x3=1是不是3-CNF-SAT满足的，只要我们看看表达式中是否有形如x+y’+z的子句，还要检查相同变量的x’+y+z’形子句，如果两者都出现，一定是不满足的。如果两形子句皆无，说明其与函数无关。
形如x+y’+z子句和对应的x’+y+z’形子句，我们称之为“互反子句”。互反子句出现一定不满足。其它情况可以用消去因子法验证。
例如f(x1,..., x6)= (x1+x1'+x2')(x2+x3+x4)(x1'+x3'+x4')(x1'+x2+x5')(x2+x3+x6)(x1+x5+x6')中，只有(x1'+x2+x5')没有(x1+x2'+x5)，那么可以肯定说明x1=0，x2=1，x5=0不一定是不满足的。用消去法将值为1的子句逐一消去：
令x1=0, 得(x2+x3+x4) (x2+x3+x6)(x1+x5+x6')
再令x2=1, 得(x1+x5+x6')
最后若x5=0，可设x6=0,得f(x1,..., x6)=1。说明有x1=0，x2=1，x6=0是满足的。
不知你是否实际设计过逻辑电路？如果设计过，一定清楚：值为1，用逻辑变量表示；而值为0时，要用逻辑变量的非来表示的。按照这种逻辑表达式抽象的表示方法，确定k位二进制数是否是k-CNF-SAT满足的，只要查看是否有相应表达形式的子句，再看看有无对应的反子句，就可以做出判断是否需要验证的决定。
要谈的问题很多，以上所谈，严格的定义与证明我会另文给出。根据我的经验，搞学术研究万不可以落入俗套，否则会庸扰自己难以自拔。解决的办法就是用实例检验，深入进去，常会有一新的感觉。我虽然涉猎P/NP问题较晚，但数学与计算机却是我的老本行，深浅程度讨论中自见分晓，切莫以非专业视吾，耽误了我们之间非常有意义的探讨。
这里所谈只是部分理解，不对之处欢迎再次批驳。
2015-7-2
https://blog.sciencenet.cn/blog-340399-902157.html
上一篇：谁说P≠NP？中国人的智力要让世界震惊！
下一篇：一位中学生计算机人才的来信
