论子句消去算法的多项式时间复杂度

姜咏江

（对外经济贸易大学 北京 中国 100013）    2016-10-30

摘  要  本文重点论证SAT问题算法时间复杂度问题。文中给出了运用子句消去法求SAT满足解的基本方法，并对该算法的每一步骤都进行了时间复杂度深入分析，进而论证出用子句消去法去求解SAT问题，最坏的情况下，算法时间复杂度也不会超过O(n^k)。作者定义了子句块和关联段的概念，并用限位数理论和方法找到了求SAT满足解的一般方法。这是本文作者所特有的研究成果。

关键词  SAT多项式时间子句消去法变量关联段限位数反子句

中图法分类号  TP301.6 O158

1.              引言

2016年10月10日在唐山召开了中国计算机应用大会。依据会议要求我投去了《子句消去法求k-SAT满足解》论文。经过大会组织审稿，决定推荐到国内一流计算机期刊发表，虽经向不同期刊推荐，但期刊不敢发表，皆是无理由退稿。既然国内期刊不能发表，我不如自己在科学网上发表^[1]，文责自负，有何不可？

论文贴到我的博客之后，有人对变量2可选解的情况提出疑问，认为这仍然是概率解的方法，对算法多项式时间复杂度不理解。本文在那篇论文的基础上，专门论述子句消去法的算法多项式时间复杂度问题，以便打消关心子句消去法读者的心头疑虑。

2.              子句消去法算法

子句消去法求SAT满足解或k-CNF=1解的算法如下：

（1）化简：将变量有唯一表现值设定为解，将相关子句消去；

（2）去掉子句块中重复子句；

（3）判断变量可选解，无可选解转（10）；

（4）变量有2个可选解，记录可选解数量，选择另一变量，转（3）；

（5）变量有唯一可选解，确定该变量唯一解，消去相关子句；

（6）对剩余子句重复（1）至（5），若全部变量设置完成（无剩余子句）转（9）；

（7）对剩余全有2个可选解变量，从任意一变量设定解出发，依据变量唯一解消去子句；

（8）有剩余子句且有变量值未设定转（7）；

（9）得满足解结束。

（10）无解结束。

3.              重要概念与定理

为了很好论证，需要重点重复几个概念和定理。

定义7. 运用子句消去法，不使剩余关联子句块无解的变量值，叫变量可选解。

理解这个概念举例说明最好。

表1是求变量x15可选解的操作过程：（1）设x15=1，消去该列表现值为1的子句；（2）由子句块x2x15知x2必取值0，消去这个子句；（3）又知x20必取值0，消去此列表现值为0子句。得到剩余的子句块全是多解。

表1  求x15=1可选解

定理3. SAT有解，其子集有解。

这个定理的重要性在于能够检查前面设定的变量值能否是关联段解的一部分。同时能够对全2可选解变量组成的关联段找到段解。

4.              变量关联段与子集

在求变量可选解的过程中，涉及消去子句的那些子句块显然也是一个SAT，我们不妨称之为变量关联段。显然，当变量有可选解的时侯，变量关联段就有解。

如果我们原来的SAT施行子句消去法，那么变量关联段中的子句就可能被消去，这样就会得到原来变量关联段的子集。

例如，表2中已知每个变量都有2个可选解，所示的是变量x15取值1时的变量关联段。其中x2、x15、x20的值0、1、0叫这个变量关联段的解。

表2  变量x15=1关联段

如果先取值x17=1，消去相关子句。对变量x15=1关联段来说，就有4、5两行的子句被消去了，剩下的1、2、3、6、13、14行子句就构成了子集。

由定理3，我们极容易得到下面的2个推论。

推论1：变量关联段子集也是原变量值的关联段。

推论2：两个可选解变量不消去，总有两个可选解。

由这个推论，下面定理7的证明就太容易了。

定理7. k-SAT或SAT的每个变量都有2个可选解，那么从任意一变量确定值出发，消去子句块变量唯一解相关子句，如此继续，可得到它们的满足解。

表3  剩余的变量关联段

证明：由推论2知，设定一个变量值，按照变量关联段解进行设定相关变量值，得到其余剩余子句都是某变量关联段的子集组成部分，每个变量仍然有两个可选解。如此继续，最多不超过全部n个变量次操作，就可以得到原来k-SAT或SAT的满足解。

5.              子句消去算法多项式时间复杂度

定理8：子句消去法是多项式时间复杂度算法。

证明：算法第（1）步的时间复杂度为O(n)。

第（2）步的k阶子句块中因k是常数，即子句块中变量的数量不变，那么子句块中子句最多不超过2^k个，所以这步操作的时间复杂度不会超过一个常数，即是O(1)，Cn^k个子句块计算的时间复杂度为O(n^k)。

第（3）步剩余变量最多有n个，判断一个变量可选解的子句块数量最多不超过2^kC_n^k+2^k-1C_n^k-1+...+2C_n¹个，要对这些子句块进行无解、唯一解和多解的判断，这是一个不超过O(n^k)时间复杂度的过程。对每个变量最坏要设置0和1进行检验的情况，最多要进行时间复杂度为2n倍的O(n^k)，即要进行时间复杂度不超过O(n^k+1)的操作。

第（4）步是转移判断。

第（5）步是对第（3）步有可选解操作的重复。

第（6）步是转移判断。

第（7）步根据定理7不难说明每消去一个变量的时间复杂度不超过O(n^k)，那么即使有n个变量有2个可选解，运用子句消去法，算法时间复杂度也不超过nO(n^k)，即不超过O(n^k+1)。

第（8）（9）（10）步是常数时间复杂度。

整个子句消去法是有限步骤完成的过程。依据算法多项式时间复杂度的性质知道，子句消去法算法的时间复杂度最坏为O(n^k+1)。

定理8证毕。

请参阅：

[1] http://blog.sciencenet.cn/blog-340399-1009188.html

2016-10-31