基于3SAT问题说明子句消去法的多项式时间复杂度

姜咏江

为让大家能理解子句消去法的多项式时间复杂度特性，本文就以3SAT问题来简单说明。三个变量的子句在施行子句消去法的过程中，也会出现一个变量或两个变量的子句。因而3SAT问题实际就是最高阶是3的SAT问题。

算法：

（1）子句消去法先查找子句块变量无解和唯一解。有变量无解计算结束，不然连续消去唯一解剩余子句块，出现变量无解结束计算，出现剩余子句块全多解时，选择另外子句块变量唯一解操作。

（2）没有了子句块变量唯一解，就去找关联变量（属于不同子句块的变量）的可选解。这一过程中需要对变量0值和1值分别施行子句消去测试可选解的数量。如果变量测试有唯一可选解，就按照（1）的方法计算，不然标记这个变量有2个可选解，然后选择另外的关联变量测试。

（3）剩余SAT全部变量都有2个可选解。此时计算最为简单，只要任意设定一个变量的值后，施行子句消去法，最终就可以得到SAT的满足解。

复杂度：

假设3SAT的每个子句块都没有唯一解变量，而且每一个变量都是关联变量，并且n个变量都需要判定可选解的数量。这应该是3SAT求满足解时间复杂度最坏的情况。

A.                  查找无解和唯一解。由于3SAT的子句块最多有C_n³个，每个子句块最多有8个子句。有8个子句的子句块存在，3SAT无解。子句块中一个变量只有4个相同值就有唯一解。所以最坏的情况下，这些特点都不会出现。这只要对每个子句块变量进行0和1的统计就可以做到。因而最多要统计8C_n³次。可见时间复杂度为不超过O(n³)。

B.                   确定变量可选解。假设测试变量是所有子句块的变量，那么设定值为0 和1都要对每个子句块确定一次无解或无变量唯一解。检查的子句块仍然不会超过C_n³个，最多要统计8C_n³次。故这步算法的时间复杂度也不超过2nO(n³)，即为O(n⁴)。

C.                   确定了每个变量都有2个可选解消去子句。由于有定理保证，所以按照子句消去法设定各变量的值，消去子句的时间复杂度显然是不超过O(n)。

从这3步操作来看，不过是有限个多项式时间的和而已，故可知3SAT问题子句消去法求解的时间复杂度最坏是O(n⁴)。

2016-12-8