The complexity of homomorphisms and renamings for minimal unsatisfiable formulas

DOI10.1007/s10472-005-0422-8zbMath1099.68040OpenAlexW4256737158MaRDI QIDQ1777396

Hans Kleine Büning, Dao-Yun Xu

Publication date: 13 May 2005

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-005-0422-8

zbMATH Keywords

complexityhomomorphismgraph isomorphismrenamingminimal unsatisfiable formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Short proofs for tricky formulas
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• On the complexity of H-coloring
• The complexity of facets resolved
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Homomorphisms of conjunctive normal forms.
• Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency.
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• The symmetry rule in propositional logic

This page was built for publication: The complexity of homomorphisms and renamings for minimal unsatisfiable formulas