振奋！每个华人一看就会做这个世界难题

将若干个逻辑变量及其非的形式“或运算”组成的表达式，再进行“与运算”，这些变量都取什么值会使结果为“真”？这就是所谓的世界难题SAT。

以往SAT问题没有快速求解方法，上百个变量，即使用计算机也无法在短时间内求出能够成立的满足解。下面介绍的子句消去法只要你熟悉汉字，会做算术题，就能快速地计算出SAT问题的满足解！

1.    用0和1表示题目

CNF=(x₁’+x₂’+x₃’)(x₁’+x₂+x₃’)(x₁+x₂’+x₃)(x₁+x₂+x₃’)(x₁’+x₃+x₄’)(x₁’+x₃+x₄)(x₃’+x₄’+x₆)(x₃+x₅’+x₆’)(x₃’+x₅’+x₆+x₁₀)(x₃+x₅+x₆+x₁₀)(x₆+x₇+x₈’)(x₆+x₇’+x₈) (x₆’+x₇ +x₈’)(x₈’+x₉)(x₈+x₉)(x₁₀’)             

CNF是SAT题目，“+”是或运算符号，“’”是变量非运算符，与运算符省略。用“1”表示x，用“0”表示x’，CNF就可以用表1来表示。

表1

2.    子句块和变量唯一解

CNF每个括号内的多项式叫子句。变量相同的子句称为子句块。有k个变量的子句块叫k阶子句块。k阶子句块最多能有2^k个子句，这个子句块称为完全块。

判定无解：有完全块的CNF一定没有结果为“真”的解！

判定变量唯一解：k阶非完全块有2^k-1个“0”或“1”，它就是这个变量的唯一解。

3.    解题方法（1）    消去变量唯一解子句

首先检查变量唯一解，有则设定这个变量值，消去这个变量有这个值的子句。如表1中二阶子句块x8x9和一阶子句块x10都有变量唯一解，所以设定x9=1,x10=0，然后消去相关子句。结果见表2。

表2

（2）    找出变量唯一可选解

逻辑变量只能取值0和1。如果一个变量不论取值0还是1，消去相关子句都会剩下完全块或矛盾值，那么就知道CNF没有“真”值解。如果只有一个值使剩下的是完全块或矛盾值，那么就可以取这个变量的另外一个值，消去相关子句（两个值都剩下非完全块，暂时不设定这个变量值）。例如x1=1会剩下完全块相互矛盾（见表3）。

表3

当测试x1=1消去相关子句时，出现了完全块冲突（黄色），因而x1=1不是可选解。如果选定x1=0消去相关子句，如表4所示，没有完全子句块及变量唯一解矛盾。因而可以设定0是x1的值，消去相关子句后继续求解。

注意：0和1都不是变量可选解，那么CNF没有“真”值解！

表4

（3）    只看关联变量可选解

确定变量可选解不必全做，只要看同属于不同子句块的变量就可以。非完全块不是关联变量一律有2个可选解（可证明）。

检测表4的关联变量x3和x6的可选解，知道0和1都是。

（4）    任选变量值消去变量唯一解相关子句

剩下的变量都有两个可选解的时侯,有定理保证一定有解。这样就可以任意确定一个变量值，消去相关子句，再确定变量唯一解，消去相关子句。重复操作，直至没有剩余子句，最终就求出了CNF结果为“真”的满足解了。表5至表8表示了操作过程。

表5  选择x6=1消去子句

表6       选择x3=1消去子句

表7  选择x2=1消去子句

表8  选择x7=1消去子句

（5）    验算

对于子句消去法计算得到的全体变量值是否是CNF=1的解，是可以验证的。一种办法是将每个变量求出的值（空白可以任意取值0或1），代入CNF的逻辑表达式，检验最终结果是否是CNF=1。

介绍一个简单的验证方法，即将所求解值置入原题（表1）的上面，检验每一行是否有与其变量值相同的子句表现值。若有，则将子句消去，若最终没有子句剩下，就说明得到的解完全正确。

本题如果x₇不选，令 x₈=0，也可将全部子句消去，从而完成解的验证。

表9  验证CNF=1的满足解

4.    华人不聪明吗？

说华人不聪明是一种偏见。这个世界难题如此简单就解决了，是不是聪明智慧的表现？

据说SAT问题找到多项式时间复杂度算法就解决了P versus NP问题。P=NP。

方法是简单的，理论是深刻的。

给一个100个逻辑变量的SAT题，大家可以试试。

3SAT100.xls （答案在下面附件）。

复件 3SAT100.xls

参阅：

http://blog.sciencenet.cn/blog-340399-1009188.html

http://blog.sciencenet.cn/blog-340399-1011907.html