可满足性问题的研究综述  

A Survey of Algorithms for SAT Problem

作　　者：王建新[1] 管利娜[1] 江国红[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《计算技术与自动化》2009年第4期138-143,共6页Computing Technology and Automation

基　　金：国家自然科学基金项目(60773111);国家973前期研究专项资金项目(2008CB317107);国家教育部创新团队资助计划项目(IRT0661)

摘　　要：对SAT问题及其各种约束子问题进行分类并给出具体定义,着重介绍常规SAT问题、最大可满足性问题(MAX-SAT)和参数化SAT问题的相关算法,并对参数算法中运用的技术进行分析和比较,提出一些SAT问题研究中值得关注的几个方面。We divide SAT problem and the constrained sub--problems into several classes provided with the corresponding definitions, and focus on the introduction of relevant algorithms for SAT problem, MAX SAT problem and parameterized SAT problems. This paper gives a detailed description about the analysis and comparison of techniques involved in the parameterized algorithms for parameterized SAT problems and presents some research orientation in research on the SAT problem.

关 键 词：可满足性问题 NP完全问题 参数计算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]