子句消去法 k-CNF=1 求满足解的算法如下（原文见附件）： （1） 化简：将变量有唯一表现值设定为解，将相关子句消去； （2） 去掉子句块中重复子句； （3） 判断变量可选解，无可选解转（ 10 ）； （4） 变量有 2 个可选解，记录可选解数量，选择另一变量，转（ 3 ）； （5） 变量有唯一可选解，确定该变量唯一解，消去相关子句； （6） 对剩余子句重复（ 1 ）至（ 5 ），若全部变量设置完成（无剩余子句）转（ 9 ）； （ 7 ） 对剩余全有 2 个可选解变量，从任意一变量设定解出发，依据变量唯一解消去子句； （ 8 ） 有剩余子句且有变量值未设定转（ 7 ）； （ 9 ） 得满足解结束。 （ 10 ） 无解结束。 要证明算法时间复杂度为多项式类型，就应该指出其每一步都是多项式类型时间复杂度。我们分步来解释： 第一步，化简的过程是判断每个变量的全部表现值是否相同。 即使一个一个表现值进行对比，由于 k-CNF 最多有 2 k C n k 个子句，而且表现值只有 0 和 1 ，那么最多需要也就是 2 k C n k 次。可以知道最坏的情况下的时间复杂度为 O( n k ) ，实际上具有相同变量的子句数会远远低于这个数。 我们只要计算一下 0 和 1 的数量，只要有一个计数为零，那么就可以设定另一个值。这时的时间复杂度为 O(1) 。 如果消去子句的过程也考虑，那么最坏也是最好的时间复杂度为 O( n k ) ，此时就没有必要再继续考察变量了，因为所有的子句都可以消去了。 第二步，去掉子句块中重复的子句的工作是在子句块中完成的。 k-CNF 的子句块最多有 2 k 个，无论你如何比较结果都不会超过常数 2 k ！，因而这一步的时间复杂度为 O(1) 。 第三步，判断变量可选解，最多要判断 2 n 次，还可以如下理解。 由于逻辑变量是定义在｛ 0 ， 1 ｝这个集合上的，因而必须对选择的变量分别选择 0 和 1 运用变量唯一解子句消去法检查是否会出现无解剩余子句块或多解剩余子句块。由于子句块最多有 C n k 个，所以需要考察的剩余子句块不会超过 C n k 个。 0 和 1 各进行一次，那么这一步算法时间复杂度也是 O( n k ) 。 第四步，这是简单判断，显然算法时间复杂度为 O(1) 。 第五步，变量确定只有唯一解。 当变量只有一个可选解的时侯，这个可选解就是变量的唯一解。消去含有这个变量这个表现值的所有子句，最多也不超过 2 k C n k 个。因而这一步算法时间复杂度不超过 O( n k ) 。 第六步，这是对（ 1 ）至（ 5 ）的有限次重复。 第七步，如果对可选解考察得到的是每个变量都有 2 个可选解。这时只要对任意一个变量取 0 或 1 的值，消去相关子句，然后再消去剩余降阶子句块中变量唯一解的子句。根据变量可选解的确定过程知道，这一过程中成为唯一解的变量相关子句都会被消去，而剩下的子句中的变量一定还有 2 个可选解。于是可以继续对剩下的子句集再进行这样的操作，直至全部子句消去。变量都有 2 个可选解的子句块最多有 C n k 个。所以这一步最坏的算法时间复杂度也不超过 O( n k ) 。 这一步不好理解的地方是任意设定一个变量的值就能够将关联段的子句全部消去吗？是不是会产生没有解的情况？如果出现没有解，再去重复求解，不就变成了概率求解了吗？ 实际情况是当每个变量都有 2 个可选解到时候，可以按照子句消去法，从变量的任意值出发，都可以求出满足解，不会出现没有解的情况，这是由变量可选解的定义直接相关的。变量的可选解是通过子句消去法剩余各阶有无解定义的，和变量可取值是不同的概念。 第八、第九、第十步都是 O(1) 这样的算法时间复杂度。 总之，依据多项式时间复杂度复杂度的低阶不算的特性，有限次的 O( n k ) 之和的算法时间复杂度仍然是 O( n k ) 的特性，用子句消去法求 k-SAT 满足解的算法时间复杂度为 O( n k ) 。 姜咏江 2016-10-19 附件： 2016子句消去法求k-SAT满足解.pdf
标签: k-SAT满足解
