一类可分离SAT问题的O(1.890n)精确算法
来源：软件学报杂志2018年第12期北京时间：
作者：黄金贵,王胜春
单位：黄金贵，湖南师范大学 信息科学与工程学院, 湖南 长沙 41008111,王胜春，湖南师范大学 信息科学与工程学院, 湖南 长沙 41008102
摘要：布尔可满足性问题（SAT）是指对于给定的布尔公式，是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题，一般认为不存在多项式时间算法，除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT），从全局搜索到局部搜索，给出了大量的相对有效算法，包括随机算法和确定算法.目前，最好算法的时间复杂度不超过O（（2-2/k）n），当k=3时，最好算法时间复杂度为O（1.308n）.而对于更一般的与子句长度k无关的SAT问题，很少有文献涉及.引入了一类可分离SAT问题，即3-正则可分离可满足性问题（3-RSSAT），证明了3-RSSAT是NP完全问题，给出了一般SAT问题3-正则可分离性的O（1.890n）判定算法.然后，利用矩阵相乘算法的研究成果，给出了3-RSSAT问题的O（1.890n）精确算法，该算法与子句长度无关.
关键词：可满足性问题;NP完全问题;正则可分离性;精确算法;算法复杂性
基金资助：国家自然科学基金（61271264，11471110）
