3-SAT问题中如何选择算法操作对象？

姜咏江

计算机科学中的3-SAT问题之所以成为NP问题，是因为算法的操作对象选择变量造成的。将操作对象选择为子句，就会设计出多项式时间复杂度算法，从而就找到了NP-complete问题转化成P类问题的基本方法。

一年前我创造的“子句消去计数法”称为“子句标志消去法”更为恰当，因为那些子句计数器就是起到一个标志的作用。

子句标志消去法就是将3-SAT问题的操作对象选择为子句，从而避开了以变量为操作对象的穷举法，成为了最直接的多项式时间复杂度的算法。

以附录中与田文洪老师讨论的问题为例，其中变量x和y都有n个，变量的总数为2n个。转化成n-CNF之后，如果以变量做为操作对象，那么算法的规模即为2n。由于每个变量可以取值0和1，故每次操作对象的值都具有不确定性，这就造成算法的众多分支，形成了算法的树形结构。

子句标志消去法以此例中的子句为操作对象，由于每个子句的值是确定的，而将子句数m做为规模，其标志值就在0～2²ⁿ-1这些2n位二进制数中间，则对于每个子句只要进行一次标志查找，就可以实现操作的结果，而无需对同一个子句进行反复操作。因而子句标志消去法这个算法时间复杂度就是O(m)。

读者不难理解，子句标志消去法对3-SAT，k-SAT，n-SAT同样适用。

2016-7-2

附录：

[11]田文洪  2016-7-1 09:47 

姜老师，需要说明一下您建议的方法如何避开CNF子项数量是2^n的?这个输入若是我第一个评论中的例子，例如把(x1∧y1) ∨ (x2∧y2) ∨ ... ∨ (xn∧yn) 变成CNF（conjunctive normal form）的例子：

(x1∨x2∨…∨xn) ∧
(y1∨x2∨…∨xn) ∧
(x1∨y2∨…∨xn) ∧
(y1∨y2∨…∨xn) ∧ ... ∧
(x1∨x2∨…∨yn) ∧
(y1∨x2∨…∨yn) ∧
(x1∨y2∨…∨yn) ∧
(y1∨y2∨…∨yn).

这是输入的话，您建议的方法是如何做的?

博主回复(2016-7-1 12:26)：1.将其它逻辑表达式转化成k-CNF的过程不应该算到求k-CNF=1的满足解算法。
2. k-CNF=1求解穷举法是以变量个数n做为规模来计算的。操作的对象是逻辑变量，对每一个逻辑变量设值都有不确定性，才会产生指数级的重复执行。
3. 用子句标志消去法是以子句数m为规模来计算的。操作的对象是子句，且每个子句的表示值是确定的，施行消去的的过程没有不确定性，因而对每个子句来说这是一个连续确定的操作过程。
4. 子句数m的变化范围也是正整数集，并且是由k-CNF中的子句数来确定的，子句的变量构成与变量数n有关，变量多，子句的构成会多一些，然而子句数量m却在一定范围内是自由的。取值4096以内整数的变量x和取值2^12以内的整数的变量m没什么区别。不能因为2^12是n=12时的2^n，就认为m与x完全不同。
5. 此例的n只是k＝n而已，实际上变量的数量，如x和y的数量对等，变量数至少是2n。但不论变量数有多少，由于子句不可重复，子句数m取值总是自然数有限序列，而子句标志不论变量个数有多大（其到达某值N）子句标志数也是一个有限正整数，最多也不会超过2^N个。