The complexity of some subclasses of minimal unsatisfiable formulas.
From MaRDI portal
complexitydisjunctive splittingmarginal MUmaximal MUminimal unsatisfiable formulasunique satisfiability
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
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
Cited in
(16)- An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
- On the structure of some classes of minimal unsatisfiable formulas
- The complexity of read-once resolution
- Minimal unsatisfiability and minimal strongly connected digraphs
- The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
- Extension and equivalence problems for clause minimal formulae
- On subclasses of minimal unsatisfiable formulas
- Two tractable subclasses of minimal unsatisfiable formulas
- On the query complexity of selecting minimal sets for monotone predicates
- The complexity of minimal satisfiability problems
- Complexity results on minimal unsatisfiable formulas
- How Many Conflicts Does It Need to Be Unsatisfiable?
- The complexity of minimizing FBDDs. (Extended abstract)
- Theory and Applications of Models of Computation
- Classes of propositional UMU formulas and their extensions to minimal unsatisfiable formulas
- The complexity of variable minimal 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)
