The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
From MaRDI portal
Publication:1777396
DOI10.1007/s10472-005-0422-8zbMath1099.68040MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
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