×

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
PDF BibTeX XML Cite