The complexity of minimal satisfiability problems

DOI10.1016/S0890-5401(03)00037-3zbMath1082.68036OpenAlexW2085138240MaRDI QIDQ1887137

Lefteris M. Kirousis, Phokion G. Kolaitis

Publication date: 23 November 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00037-3

zbMATH Keywords

dichotomy theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (11)

Filter-based resolution principle for lattice-valued propositional logic LP\((X)\) ⋮ On the Boolean connectivity problem for Horn relations ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ On the tractability of minimal model computation for some CNF theories ⋮ On the parameterized complexity of non-monotonic logics ⋮ The complexity of circumscriptive inference in Post's lattice ⋮ Trichotomies in the complexity of minimal inference ⋮ On the counting complexity of propositional circumscription ⋮ Isomorphic implication ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Graph-based construction of minimal models

Cites Work

• A dichotomy theorem for maximum generalized satisfiability problems.
• On the complexity of H-coloring
• The directed subgraph homeomorphism problem
• Circumscription - a form of non-monotonic reasoning
• Structure identification in relational data
• The complexity of model checking for circumscriptive formulae
• Conjunctive-query containment and constraint satisfaction
• Complexity of generalized satisfiability counting problems
• The Approximability of Constraint Satisfaction Problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Inverse Satisfiability Problem
• Closure properties of constraints
• On generating all solutions of generalized satisfiability problems
• The complexity of satisfiability problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of minimal satisfiability problems