谷文祥，姜蕴晖，周俊萍，殷明浩

(1.东北师范大学计算机科学与信息技术学院，吉林长春 130117;2.长春建筑学院基础教学部，吉林长春 130607)

人工智能研究领域存在着很多计算困难的问题，如 SAT(satisfiability)问题、QBF(quantified boolean formula)问题、智能规划问题、模型诊断问题等.若P≠NP成立，人们将无法为这些问题找到多项式时间的求解算法.这时从理论上分析这些问题在最坏情况下的时间复杂性上界尤为重要，因为此时对该上界的一个微小的改进，例如从O(ck)改进为O((c－ε)k)，就会使得问题求解的算法在效率上获得指数级别的提高.以SAT问题为例，作为第一个被证明是NP完全的问题，改进其在最坏情况下的时间上界受到了研究人员的广泛关注.MaxSAT(maximum satisfiability)问题是SAT问题的扩展，它指的是给定一个命题逻辑公式，找到一组使真值赋值同时满足最多的子句.与SAT问题一样，MaxSAT问题在计算机科学领域有着十分重要的地位，因为它是求解人工智能和组合优化问题的基础［1-2］.当公式中子句的长度至多为2时称之为Max-2SAT(maximum two-satisfiability)问题，它是一个NP完全的问题［3］.近年来，众多学者对Max-2SAT问题进行了研究［4-7］，已经将其最坏情况下的上界缩小到O(2m/6.312)［8］.与 MaxSAT 问 题 相 对 的 是 MinSAT(minimum satisfiability)问题，它指的是给定一个命题逻辑公式，找到一组使真值赋值同时满足最少的子句.虽然人们对MaxSAT问题已经做了非常多的研究，但对MinSAT问题的研究却并不深入.目前，对MinSAT问题的求解主要采用近似方法［9-10］.此外，LI等在文献［11］中将MinSAT问题转换为Max-SAT问题，给出了一个MinSAT求解器.事实上，在求解某些组合优化问题时，将其……