QBF问题中隐蔽集的求解过程  

Solving Process of Backdoors Set in QBF

作　　者：杨俊成[1] 陶琳[1] 李淑霞[1] 

机构地区：[1]河南工业职业技术学院电子信息工程系,南阳473000

出　　处：《计算机系统应用》2016年第8期250-253,共4页Computer Systems & Applications

基　　金：河南省教育厅科学技术研究重点项目(12A520048)

摘　　要：隐蔽集作为QBF问题的重要结构之一,能使QBF这一难求解问题变得更加简单.QBF问题中隐蔽集的求解相当复杂且难以理解.为了使读者更好的理解QBF问题中隐蔽集的求解过程,本文对QBF问题中隐蔽集的求解过程进行深入研究,结合实例计算变量的深度、选择符合条件的变量x并计算其对应的三角依赖变量集Dψ^△（x）,根据B=B∪{x}={x}和ψ＇=ψ-Dψ^△（x）的思想求解出问题的隐蔽集,希望本文能为该领域的相关研究人员提供一定的参考.The Backdoors as one of the important structures of problem QBF, it makes QBF problems easier in solving difficulty. In QBF problem, the solving of backdoors is quite complex and difficult to understand. In order to enable the reader to better understand the solving process, this paper researches the solving process of backdoors for QBF problems, calculates the depth of variable x and the triangle dependent set of variable Dψ^△（x） that is meet the condition by combining the examples. This paper solves the backdoors of this problem according to the ideas of B=B∪{x}={x}and ψ＇=ψ-Dψ^△（x）. We are hoping that it can provide a reference for researchers in this field.

关 键 词：QBF问题 隐蔽集 重要结构 求解过程 

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