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

THE COMPLEXITY OF RENAMINGS FOR FORMULAS IN MAX AND MARG

作　　者：许道云[1] 

机构地区：[1]贵州大学计算机科学系,贵阳550025

出　　处：《南京大学学报（数学半年刊）》2006年第2期181-199,共19页Journal of Nanjing University(Mathematical Biquarterly)

基　　金：Supported by the National Natural Science Foundation of China (No. 60463001,No. 10410638, No. 60310213).

摘　　要：研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名(?),使得(?)(F)=H?”的复杂性．对于极小不可满足公式的子类MAX和MARG,我们证明了:其变元改名和文字改名的复杂性等价于图同构问题GI．We investigate the complexity of deciding whether for propositional CNF formulas F and H there exists a variable renaming or a literal renaming φ such that φ（F） = H. For the subclasses MAX and MARG of minimal unsatisfiable formulas, we show that the variable and literal renaming problems are equivalent to the graph isomorphism problem GI.

关 键 词：复杂性 变元改名 文字改名 极小不可满足公式 图同构 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]