MAX(1)和MARG(1)中公式改名的复杂性(英文)  

Complexities of Renaming for Formulas in MAX(1) and MARG(1)

作　　者：许道云[1] 董改芳[2] 王健[3] 

机构地区：[1]贵州大学计算机科学系,贵州贵阳550025 [2]内蒙古农业大学计算机与信息工程学院,内蒙古呼和浩特010018 [3]软件工程国家重点实验室(武汉大学),湖北武汉430072

出　　处：《软件学报》2006年第7期1517-1526,共10页Journal of Software

基　　金：国家自然科学基金;贵州省高层次人才科研条件特助经费;贵州省省长基金~~

摘　　要：改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题“对于给定的CNF公式H和F是否存在一个变元(或文字)改名,使得(H)=F?”的计算复杂性.MAX(1)和MARG(1)是极小不可满足公式的两个子类,这两个子类中的公式可以用树表示.树同构的判定问题在线性时间内是可解的.证明了对于MAX(1)和MARG(1)中的公式,文字改名问题在线性时间内可解,变元改名问题在平方次时间内可解.A renaming is a function mapping propositional variable to itself or its complement, a variable renaming is a permutation over the set of propositional variables of a formula, and a literal renaming is a combination of a renaming and a variable renaming. Renaming for CNF formulas may help to improve DPLL algorithm. This paper investigates the complexity of decision problem： for propositional CNF formulas H and F, does there exist a variable （or literal） renaming q~ such that ~H）=F？ Both MAX（I） and MARG（1） are subclasses of the minimal unsatisfiable formulas, and formulas in these subclasses can be represented by trees. The decision problem of isomorphism for trees is solvable in linear time. Formulas in the MAX（1） and MARG（1）, it is shown that the literal renaming problems are solvable in linear time, and the variable renaming problems are solvable in quadratic time.

关 键 词：计算复杂性 改名 极小不可满足公式 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构] O141.3[自动化与计算机技术—计算机科学与技术]