摘要
SAT命题可满足性问题的隐蔽集作为引导搜索SAT问题的关键决策变量,可以优化SAT问题的求解,成为人工智能方向的研究热点之一。本研究对SAT问题隐蔽集中的若干问题进行研究,分别从隐蔽集的概念、隐蔽集的分类进行全面分析,提出影响求解隐蔽集大小的相关因素,论述隐蔽集的参数复杂性与问题难度的关系。
The variables of backdoors are key decision variables to guide the search for SAT problems,and which optimize SAT problem solving and therefore become the one of the hot spots for artificial intelligence direction.This paper studies some problems of the backdoors of SAT problems,analyzes the concept of backdoors and classification of backdoors,proposes the factor of impact backdoors size solving,discusses the relationship of the parameters complexity of backdoors and problem difficulty comprehensively.
作者
杨俊成
李淑霞
蔡增玉
YANG Juncheng LI Shuxia CAI Zengyu(Department of Computer Engineering, Henan Polytechnic Institute, Nanyang 473000, China School of Computer and Communication, Zhengzhou University of Light Industry, Zhengzhou 450002, China)
出处
《青岛科技大学学报（自然科学版）》
CAS
2016年第5期580-583,共4页
Journal of Qingdao University of Science and Technology:Natural Science Edition
关键词
SAT问题
隐蔽集
问题类
参数复杂性
问题难度
propositional satisfiability problem
backdoors
problem class
parameters complexity
problem difficulty
