千禧难题P与NP问题（科普2）

姜咏江

2. SAT问题求解方法

P与NP问题之所以能够称为世界难题，这是因为这个问题最早要追溯到上个世纪50年代，数学家库尔特·哥德尔向计算机发明人之一冯诺依曼的提出了这个问题。1971年斯提芬.库克给出了NP类问题的定义，之后被学术界接受。现在已经有很多问题被证明了是NP问题，但是一直没有人能够确切证明NP问题就是P问题，或者NP问题不可能是P问题。其实，推翻一个证明的最好方法，就是找到一个反例。

世界各国的数学家和计算机专家都没有停止过寻找NP类问题是P类问题的例子。我是一个主张NP=P的人，因为我找到了SAT这个基本的NP类的多项式时间计算方法——子句消去法。

2.1  SAT问题的概念

 什么是SAT问题？“若干个逻辑变量和变量非形式组成的多项式，求它们与运算结果为真的解问题”就是SAT。这种逻辑运算式叫合取范式（用CNF记），每个因子多项式叫子句，单一变量的逻辑项被称为文字。例如合取范式

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=1时的10个逻辑变量值，这就是SAT问题。

合取范式CNF可以用数码“0”和“1”来表示。上面这16子句用0和1表达出来，就如表1所示，1代表变量本身，0表示变量的非形式。

表1 CNF的0和1表示

表1的表头是逻辑变量，每一行是一个子句。每列的0和1叫表头逻辑变量的表现值（文字）。求CNF=1的解写在表头的上面。

表1中相同变量组成的子句叫子句块。具有共同变量，但变量不完全相同的子句块间称为关联子句块。通过关联子句块连接在一起的全部子句块叫关联段。关联段和关联段之间没有共同的变量。

表1的全部子句块组成了一个关联段。

2.2        限位数理论

长时间人们对SAT问题没有有效地求解方法，这是因为没有找到CNF特有的内在结构特点。虽然许多人也将SAT问题用二进制数码表示，但没有新的理论支撑，也未曾找到解决的办法。

限位数是用一定位数的数码排列得到的数，它与普通数不同是无效0不能省略。限位数理论是机器算术运算设计的基础理论，又是解决纯离散数学计算的基础。

k位二进制限位数共有2^k个，其值由0直排到2^k-1。如果k位二进制数超过了2^k个，那么就一定出现了重复的数。表2列出的是3位二进制限位数，共有2³个。

从表2容易理解，全部的k位二进制限位数纵向排列，每一列0和1的数量都是2^k-1个。如果将一列的0或1的行都去掉，不考虑消去的那一列，那么剩下的那些行，就一定是k-1位的所有二进制数。这一特点就成为了子句消去法判断变量唯一解和CNF=1无解的依据。

两个数码相加结果是最大数码，称它们是互为反码。一个k位二进数的每个数码用其反码替换，得到的数叫原来数的反码数。每个表示子句的数都有唯一一个反码数。由表2不难理解这个结论。

表2  三位二进制限位数

2.3        子句消去法

CNF的子句中如果有一个文字的值是“真”，那么这个子句的值就是“真”。要求整个CNF的结果是“真”，必须全部子句的值都是“真”。根据这一原理，只要子句中有一个文字x，我们就设x为“真”，那么子句的值就是“真”，子句中有一个文字为x’，就可以设x为“假”，同样会让这个子句的值是“真”。在求CNF结果是“真”的时侯，用这种方法将子句设定为“真”之后一一去掉，只要变量不重复设值，最后全部子句都去掉了，那么设定的那些值就是使CNF为“真”的解，不然就不是使CNF为“真”的解。

上面的这种做法并不能保证每次设定的全部变量值是CNF=1的解。能不能有确定的方法让每次设定的变量值都是CNF=1的那些值？姜咏江发明的子句消去法解决了这个问题。

由表2所示子句的0和1表示方法可以知道，如果一个子句块的所有子句都存在，那么不论我们如何设定变量的值，都不可能将全部子句消去。这种情况只要看一个变量的0 和1 的数量就可以判断。如果k个变量的子句块有一个变量有2^k-1个0，同时还有2^k-1个1，那么肯定这个变量不论设定0还是1，都不可能使这个子句块的全部子句值为1。由于子句之间是与运算的关系，所以CNF中至少有一个子句的值是0，那么合取范式CNF的值一定是0，也就是CNF=1无解。

我们把k个变量的子句全存在的子句块叫完全子句块。进一步分析可知，完全子句块用设定变量值的方法，不可能将它的全部子句消去，因而CNF的值必定是0。如果我们在设定变量值的时候能够避开出现完全子句块，你就会找到满足CNF=1的解。

在设定变量值的时候，能不能避开完全子句块呢？这一点我们现在可以做到了。根据前面的限位数理论，如果一个k个变量的子句块中，有一个变量有2^k-1个相同的0（或1），而不同时有2^k-1个相同的1（或0），那么设定这个值，消去子句，就不会有k-1个变量的剩下完全子句块，即设定这个变量值就不会使CNF=1无解。这种情况下的变量称为有唯一解。

规则1：子句块变量有唯一解必须首先设定。

表1中的子句块x₁₀和子句块x₈x₉就属于规则1的情况。设定x₁₀=0，x₉=1，然后消去值为1 的子句，得到表3。

表3  设定唯一解消去子句

表3中剩下的子句块中没有唯一解的变量了。剩下的子句块形成了一个关联段。由于每个逻辑变量都只能取值0或1，我们不妨设定0 或1，看看会不会使CNF=1无解。如果无解，这个值肯定不能选，但不能就完全确定CNF=1无解，还要看看另外一个变量的值。这就有了变量可选解的概念。

什么是变量可选解呢？

在无变量唯一解的CNF中设定变量的一个值，并消去使值为1 的子句后，剩下子句块按照变量唯一解继续消去子句，如果剩下的子句块中没有变量唯一解，且子句块都不是完全子句块，则称设定的那个变量值是变量可选解。

根据可选解的定义，如果剩下的子句块有完全子句块，那么这次最初设定的变量值就不是它的可选解。由于逻辑变量可以取0和1两个值，于是还可以查看另一个值是不是可选解。如果只有一个值是可选解，那么这个值就一定是变量在关联段中的唯一解，如果0 和1 都不是变量的可选解，那么CNF=1是不会有解的。如此，求CNF=1的解在无法确定变量唯一解的情况下，必须象除法运算一样，先要“试值”，然后才能确定变量的取值。

对于表3的剩余CNF，我们先测试x₁=0，消去子句，发现剩余子句块没出现变量唯一解和完全子句块，这说明0是x₁的可选解（见表4）。

我们再测试x₁=1，消去子句，发现x₁=1剩余子句块x₂ x₃和x₃ x₄出现了唯一解矛盾，即x₃无法取值。这说明1不是x₁的可选解（见表5）。

由此我们得出了0是x₁在关联段中的唯一解。按照表4 的过程来设定x₁=0，消去子句，得到表6。

表4  x₁=0是可选解

表5  x₁=1不是可选解

表6  剩下的子句块

对于无变量唯一解的子句块组成的关联段，有定理可以证明“非关联变量一定有2个可选解。”因而测试变量可选解只要对关联变量进行就可以。对于表6的关联段，只要测试x₃和x₆的可选解数量即可。

象测定x₁的可选解一样，测出x₃和x₆都有2个可选解。于是知，表6 剩余的CNF的每个变量都有2个可选解。根据变量可选解的定义，随便设定一个变量的0 或1值，都不会在消去子句后出现完全子句块，也即不会出现无解。因此可以有

定理：由全是2个可选解变量构成的CNF，任意从一个变量设定值，用变量唯一解消去子句，最后总可以得到CNF=1满足解（这个定理的证明请见附件）。

对于表6，我们设定x₆=1，再设定x₃=1，消去相关子句，得到表7。

表7  设定x₆=1，再设定x₃=1

表7 的x₂有唯一解1。而x₇，x₈只要设定x₇=1，或x₈=0，就可以将全部子句消去，从而知011**11*10获011**1*010都是表1的CNF=1的满足解。

2.4        验证子句消去法的满足解

子句消去法计算得到的全体变量值是不是CNF=1的解？这是可以验证的。一种办法是将每个变量求出的值（*可以任意取值0或1），带入CNF的逻辑表达式，看看最终结果是不是1。

这里介绍一个简单的方法，就是将结果放到表1的上面，看看每一行是否有与上面变量值相同的子句，有则将子句消去，最终没有子句剩下，就说明是解，不然就说明计算的过程出现了错误（见表8）。

表8  满足解验证

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

2.5        总结

完成用子句消去法求SAT问题满足解要运用两个规则。

规则1：子句块变量有唯一解必须首先设定。

规则2：子句块无变量唯一解，先设定变量唯一可选解。

SAT问题长期没能解决的原因是没有得到其特殊的结构规律造成的。

我相信，只要能够找到NP问题的具体规律都会通过计算推导的方法获得解决。

关于理论上的子句消去法深层次证明请看：

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

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

2016-11-19