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
- scientific article; zbMATH DE number 1688380 (Why is no real title available?)
- Complexity results on minimal unsatisfiable formulas
- How Many Conflicts Does It Need to Be Unsatisfiable?
- scientific article; zbMATH DE number 1418344 (Why is no real title available?)
- 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)
