The complexity of some subclasses of minimal unsatisfiable formulas.
From MaRDI portal
Publication:5309031
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)
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
(15)- On the query complexity of selecting minimal sets for monotone predicates
- scientific article; zbMATH DE number 1688380 (Why is no real title available?)
- Classes of propositional UMU formulas and their extensions to minimal unsatisfiable formulas
- On the structure of some classes of minimal unsatisfiable formulas
- The complexity of variable minimal formulas
- The complexity of read-once resolution
- The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
- Theory and Applications of Models of Computation
- 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?
- scientific article; zbMATH DE number 1418344 (Why is no real title available?)
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)
