论文部分内容阅读
研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名(?),使得(?)(F)=H?”的复杂性．对于极小不可满足公式的子类MAX和MARG,我们证明了:其变元改名和文字改名的复杂性等价于图同构问题GI．
We study the problem of determining whether the complexity of (?) (F) = H? Exists for a variable (or literal) renaming (?) For the propositions CNF formulas F and H. For the subgroups MAX and MARG of the smallest unsatisfiable formula, we prove that the complexity of the renaming and renaming of the arguments is equivalent to the GI isomorphism problem.