博文
子句消去法求k-SAT满足解(正式发表），附件是正式版
|||
子句消去法求k-SAT满足解
姜咏江
（对外经济贸易大学北京中国 100013）
（没法直接写公式，只好将2016...pdf文件放在后面。）
摘 要 本文将k-SAT问题用表格式表达，用限位数理论和方法找出了k-CNF特有规律，用作者发明的变量唯一解消去法，能够在多项式时间求出k-SAT的满足解。算法通过证明和大量k-SAT问题实例检验正确无误。
关键词 k-SAT 子句消去法 限位数 多项式时间反子句
中图法分类号 TP301.6 O158
Remove-Clause method for solving k-SATSatisfied Answer
JIANG Yong-Jiang
( University of International Business and Economics，Beijing CHN 100013 )
Abstract In this paper, the k-SAT problem is expressed in the form of table, using the limit number theory and method to find out the unique law of k-CNF, using the author's invention of the unique answer of the variable Remove-Clause method, can be in polynomial time to find the answer of k-SAT. Algorithm through the proof and a large number of instances of k-SAT problems to test, they are all correct.
Key words k-SAT Remove-Clause Limited-Number Polynomial-time Opposite-Clause
1. 引言
P/NP问题是计算机与数学科学界一大难题[1]。自从1971年斯提芬.库克[2]提出NP-complete类问题之后，理论学界普遍认为，只要能够找到任何一个NP-complete问题的多项式时间复杂度算法，就可以确定NP类问题就是P类问题。进而认为对那些用计算机都计算缓慢的问题，也可以找到快速的算法[1]。
40多年的时间过去了，人们找到了众多NP-complete问题，典型的有SAT问题、3-SAT问题及其一般化的k-SAT问题、哈密顿回路问题、旅行商问题、子集和问题等。但这些问题至今都无有公认的多项式时间复杂度的算法。许多人将此类问题的解决放到了未来数学家的肩上[3]。
本文作者的贡献是发明了子句消去法，用该法对k-SAT问题进行了全面的分析，利用限位数理论找到了合取范式k-CNF特有的结构规律，并可在多项式时间之内求出k-SAT满足解。
2. k-SAT与二进制限位数
一般提到的合取范式当中的子句中会同时包含逻辑变量x和它的非运算x’，这样的子句在求k-SAT问题满足解时不起作用。因而本文中不讨论变量x和它的非运算x’包含在一个子句中的情况。
2.1 k-SAT的定义
合取范式k-CNF是由k个逻辑变量或变量的非运算组成的多项式之间进行与运算的逻辑表达式，其中每一个参加与运算的多项式叫子句。多项式中的逻辑变量或者逻辑变量的非运算形式都是逻辑项，又叫文字。当k=3时的3-CNF=1求解问题，就是3-SAT问题。
下面给出合取范式k-CNF的严格定义。
定义1. 将逻辑变量x的非运算用x’表示，集合A=｛x1,x2,...,xn｝, A’=｛x1’,x2’,...,xn’｝，
k-CNF= 
其中k是一个常正整数，n0是n的最小值，k≤n0, xij∈A∪A’， xijxij’ 
，m是子句的数量。
定义2. 使k-CNF=1成立的一组变量值叫满足解。这个问题一般又叫k-SAT问题。
2.2 SAT的定义
求k-CNF=1的满足解的问题过程，会涉及到j=k，k-1，k-2，…，2，1的变化。为此，这里也要给出SAT的严格定义。
定义3. 将逻辑变量x的非运算用x’表示，集合A=｛x1,x2,...,xn｝, A’=｛x1’,x2’,...,xn’｝，
SAT=
=1
其中xij∈A∪A’，且xijxij’ ，vi是第i个子句文字数，n0是n的最小值，vi≤n0, m是子句的数量。
求=1的满足解问题一般就叫SAT问题。
限位数是用一定位数的数码排列得到的数，它与普通数不同是无效0不能省略。限位数理论是机器算术运算设计的基础理论[4]，在本文中又是子句消去法设计的基础。
k位二进制限位数共有2k个，其值由0直排到2k-1。如果k位二进制数超过了2k个，那么就一定出现了重复的数。表1列出的是3位二进制限位数，共有23个。
从表1容易理解，全部的k位二进制限位数纵向排列，每一列0和1的数量都是2k-1个，这一特点成为了子句消去法判断变量唯一解和k-SAT无解的依据。
表1 三位二进制限位数
x1 | x2 | x3 |
0 | 0 | 0 |
0 | 0 | 1 |
0 | 1 | 0 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
1 | 1 | 1 |
2.4 K-CNF数码表达形式
如果用1表示逻辑变量x，用0表示逻辑变量x的非运算形式x’，那么k个逻辑变量的子句构成的合取范式就可以用表2来表示，其中k=3。
3-CNF = (x2’ +x1’ +x0’) (x2 +x1’ +x0) (x4 +x3’ +x2’) (x4 +x3 +x2) (x4’ +x1’ +x0’)
表2不仅表示了3-CNF，而且表示子句全体的结构及其运算关系。
为了区别求解时变量的取值，将表2中子句变量对应的0和1称为变量的表现值。
表2中每一个子句占一行，同色底纹的子句具有相同的变量，称为子句块。子句块包含变量数叫子句块的阶。含有相同变量的子句块相互关联形成关联段。关联段中的子句块间称为关联子句块。
表2 3-CNF二进制数码表
x4 | x3 | x2 | x1 | x0 |
|
| 0 | 0 | 0 |
|
| 1 | 0 | 1 |
1 | 0 | 0 |
|
|
1 | 1 | 1 |
|
|
0 |
|
| 0 | 0 |
k-CNF可能有若干个关联段，关联段之间没有共同的变量，所以k-SAT的满足解可以由各关联段分别求出。
定义4. 有2k个不重复子句的k阶子句块，称为完全子句块。
由表1可知，完全子句块就是k位二进制数全体。完全子句块，每一数位（变量表现值）的0和1的数量都是2k-1个。
定义5. k阶子句块中互为反码的子句称为互反子句。
由表1可知，完全子句块中每个子句都有反子句。
3. 子句消去法与性质
由表2可见，变量的表现值是0的话，表示是这位变量的非运算。如果我们设定这位逻辑变量的值是0，通过非运算，子句的这个项值就是1，从而就表示这个子句的逻辑值是1。同样，将变量值设定为表现值是1，也是这种情况。于是可知，逻辑变量设定值与子句的变量表现值相同，那么包含该项的子句值就都是1。
依据k-CNF的定义，容易知道k-CNF=1求解中，若设定变量值，使子句的值是1，则可以将该子句消去，不影响继续求解。
二进制数表示子句的k-CNF，如果将一个变量的值设定为0或1，可使所有包含该变量这个表现值的子句值为1。那么求k-CNF=1解的问题中，这些子句都可以消去，而剩余部分可以继续这样做，直至全部的变量值都设定完为止。如果这一过程的最后没有剩余子句了，那么所设的变量值全体就是这个k-CNF=1的满足解。如果有剩余子句未被消去，说明设定的变量值使剩余子句的值为0，这组设定值就不是k-CNF=1的解。这就是子句消去法[5]。
例如，表2表示的3-CNF，若设x4x3x2x1x0=10000，就可以将全部子句消去。将这个值带入原3-CNF的文字表达式，则有3-CNF=1，说明x4x3x2x1x0=10000是一个满足解。
为了能够更清楚准确地论述问题，需要严格给出如下一些概念。
定义6. 运用子句消去法，能把子句块的全部子句消去的一组变量值叫块解。
定义7. 运用子句消去法，不使剩余关联子句块无解的变量值，叫变量可选解。
定义8. 能把关联段全部子句消去的一组变量值叫段解。
对于k阶完全子句块施行子句消去法，总会有子句不能消去。
定理1. k-阶完全子句块无可选解（k=1,2,3,…C，C是一个正整数）。
证明：因为完全子句块的每个变量的0和1表现值都有2k-1个，故无法设定变量值将子句全部消去，所以完全子句块无解。
定理2. k阶子句块中无反子句的子句是块解。
证明：因为用这个子句变量的表现值逐一消去子句后子句块不会有剩余子句。
定理3. k-SAT有解，其子集有解。
证明：显然，k-SAT的解都是子集的解。
用定理3可以将变量表现值唯一的所有子句设定该值之后，全部消去，实行化简继续求解。
定理4.属于k阶子句块，但不在其中的互反子句都是块解。
证明：将互反子句中的一个添加到子句块，依据定理2，这个子句是添加它之后的块解。再依定理3知，这个添加的子句是原子句块的块解。
定理5. 运用子句消去法，k-SAT有解的充要条件是每个变量都有可选解。
证明：（充分性）设每个变量都有可选解，依据变量可选解的定义，可知每个关联段都有解，因此k-SAT有解，充分性成立。
（必要性）假如k-SAT存在无可选解变量，则这个变量所在的关联段无解。依定理3，知k-SAT无解。
运用子句消去法每设定一个变量的值，并消去那些含有该变量表现值的子句之后，剩下的含有这个变量的子句中，这个变量值已经确定，未确定值的那些变量表现值就变成了k-1阶子句。这种过程就是降阶运算。随着变量值的设定和消去子句，子句块最后都会降到一阶。
定理6. k阶子句块的变量只有2k-1个0（或1）表现值，那么这个0（或1）是该变量的唯一可选解。
这个定理称为唯一解定理，在子句消去法中起着十分重要的作用。
证明：依据二进制限位数理论知，当k位二进制数的一位有2k-1个相同值时，其余k-1位就形成了k-1阶完全子句块。如果不设定这个表现值为变量的解，消去相关子句后，就会剩下k-1阶完全子句块，会出现这个剩余子句块变量无解。而设定该值，就会消去可能产生的剩余完全子句块。因此这个表现值就是该变量的唯一可选解。
逻辑变量可选解最多有2个。若某个变量只有1个可选解，称变量有唯一解。
如果k-SAT或剩余的SAT的每个变量都有2个可选解，那么可依据下面定理求满足解。
定理7. k-SAT或SAT的每个变量都有2个可选解，那么从任意一变量确定值出发，消去子句块变量唯一解相关子句，如此继续，可得到它们的满足解。
证明：由可选解定义可知，选择变量可选解，消去剩余子句块变量唯一解的子句，剩下的变量仍然有2个可选解，不然就被消去。继续这样操作，知最终可得k-CNF=1或SAT=1的满足解。
依据子句消去法及其性质，对分成子句块表格式的k-CNF=1求解的算法如下：
（1） 化简：将变量有唯一表现值设定为解，将相关子句消去；
（2） 去掉子句块中重复子句；
（3） 判断变量可选解，无可选解转（10）；
（4） 变量有2个可选解，记录可选解数量，选择另一变量，转（3）；
（5） 变量有唯一可选解，确定该变量唯一解，消去相关子句；
（6） 对剩余子句重复（1）至（5），若全部变量设置完成（无剩余子句）转（9）；
（7） 对剩余全有2个可选解变量，从任意一变量设定解出发，依据变量唯一解消去子句；
（8） 有剩余子句且有变量值未设定转（7）；
（9） 得满足解结束。
（10）无解结束。
定理8：子句消去法是多项式时间复杂度算法。
证明：算法第（1）步的时间复杂度为O(n)。第（2）步的k阶子句块中因k是常数，即子句块中变量的数量不变，依据定义1，子句块中子句最多不超过2k个，所以这步操作的时间复杂度不会超过一个常数，即是O(1)。第（3）变量最多有n个，判断一个变量可选解的子句块数量最多是Cnk个，最多要对k阶的个子句块进行无解、唯一解和多解的判断，这是一个不超过O(nk)时间复杂度的过程。
那么，对每个变量最坏要设置0和1进行检验的情况，最多要进行时间复杂度为2n倍的O(nk)，即要进行时间复杂度不超过O(nk+1)的操作。
定理8证毕。
P/NP问题中所谓的多项式是指k是一个小于n的常整数，n的初值可以是k，在n增长的过程中，k保持不变。不能够总有k=n的理解，因为这样nk就是幂nn，实际上没有了k，从而混淆了常量与变量的概念。
如果确实有n-CNF，那么依据子句消去法，这是一个n元变量的子句块，只要n-CNF不是完全子句块，依据定理2和定理4，总能找到n-CNF=1的满足解。这一过程只与子句的数量m有关。问题变成了在m个n位二进制数的集合中查找反码的问题。诚然有1≤m≤2n，但已绝非是与2n个数中的n有关的问题了，n仅仅是数域的一种计算量而已。
不难看出求k-SAT满足解的子句消去法，完全适合求SAT的满足解。
https://en.wikipedia.org/wiki/P_versus_NP
[2] Steven Cook. The complexity of theorem proving procedures. In Proc. ThirdAnnual ACM Symposium on the Theory of Computing, pages 151-158,1971.
[3] 楊照崑楊重駿，未來數學家的挑戰.
http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/
[4] 姜咏江自己设计制作CPU与单片机,北京人民邮电出版社2014.9，p237-243.
[5] 姜咏江 3-SAT分段子句消去法.
https://blog.sciencenet.cn/blog-340399-1009188.html
上一篇：悲哀：中国人科学原创一定要用英文发表吗？否则不算？
下一篇：子句消去法求k-SAT满足解的基本思路和练习
