摘要
对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.
出处
《计算技术与自动化》
2009年第4期138-143,共6页
Computing Technology and Automation
基金
国家自然科学基金项目(60773111)
国家973前期研究专项资金项目(2008CB317107)
国家教育部创新团队资助计划项目(IRT0661)
关键词
可满足性问题
NP完全问题
参数计算
satisfiability problem
NP-- complete problem
parameterized computation
