Complexities of renaming for formulas in MAX(1) and MARG(1)

zbMATH Open1099.68643MaRDI QIDQ5490397FDOQ5490397

Ji'an Wang, Gaifang Dong, Daoyun Xu

Publication date: 4 October 2006

Recommendations

• The complexity of renamings for formulas in MAX and MARG
• The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
• Existence of simple propositional formulas
• Recognizing renamable generalized propositional Horn formulas is NP- complete
• On renaming a set of clauses as a Horn set

zbMATH Keywords

complexityrenamingminimal unsatisfiable formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

This page was built for publication: Complexities of renaming for formulas in MAX(1) and MARG(1)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5490397)