The complexity of some subclasses of minimal unsatisfiable formulas.
zbMATH Open1137.68028MaRDI QIDQ5309031FDOQ5309031
Authors: Hans Kleine Büning, Xishun Zhao 
Publication date: 9 October 2007
Recommendations
- Complexity results on minimal unsatisfiable formulas
- On subclasses of minimal unsatisfiable formulas
- Two tractable subclasses of minimal unsatisfiable formulas
- An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
- On the structure of some classes of minimal unsatisfiable formulas
complexityunique satisfiabilityminimal unsatisfiable formulasdisjunctive splittingmarginal MUmaximal MU
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (15)
- Title not available (Why is that?)
- On the query complexity of selecting minimal sets for monotone predicates
- On the structure of some classes of minimal unsatisfiable formulas
- The complexity of variable minimal formulas
- The complexity of read-once resolution
- Theory and Applications of Models of Computation
- The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
- On subclasses of minimal unsatisfiable formulas
- Two tractable subclasses of minimal unsatisfiable formulas
- Complexity results on minimal unsatisfiable formulas
- Extension and equivalence problems for clause minimal formulae
- Minimal unsatisfiability and minimal strongly connected digraphs
- How Many Conflicts Does It Need to Be Unsatisfiable?
- Title not available (Why is that?)
- Classes of propositional UMU formulas and their extensions to minimal unsatisfiable formulas
This page was built for publication: The complexity of some subclasses of minimal unsatisfiable formulas.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5309031)
