# zbMATH — the first resource for mathematics

The complexity of renamings for formulas in MAX and MARG. (English) Zbl 1143.68407
Summary: We investigate the complexity of deciding whether for propositional CNF formulas $$F$$ and $$H$$ there exists a variable renaming or a literal renaming $$\phi$$ such that $$\phi(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.
##### MSC:
 68Q25 Analysis of algorithms and problem complexity 03B35 Mechanization of proofs and logical operations