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

MaRDI QIDQ5490397zbMATH OpenFDO

Authors Gaifang Dong, Daoyun Xu, Ji'an Wang

Publication date 4 October 2006

zbMATH Keywords

complexityrenamingminimal unsatisfiable formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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

Cited in

(1)

• The complexity of renamings for formulas in MAX and MARG

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)