Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
From MaRDI portal
Publication:5504698
DOI10.1007/978-3-540-92800-3_2zbMath1171.68495OpenAlexW1554715854MaRDI QIDQ5504698
Heribert Vollmer, Nadia Creignou
Publication date: 22 January 2009
Published in: Complexity of Constraints (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92800-3_2
Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Operations and polynomials in algebraic structures, primal algebras (08A40)
Related Items (13)
Non-local configuration of component interfaces by constraint satisfaction ⋮ Paradigms for parameterized enumeration ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ Unnamed Item ⋮ Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimal distance of propositional models ⋮ A Dichotomy Theorem for the Inverse Satisfiability Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Recognizing frozen variables in constraint satisfaction problems
- Parameterized complexity of constraint satisfaction problems
- Structure identification of Boolean relations and plain bases for co-clones
- A dichotomy theorem for maximum generalized satisfiability problems.
- Bases for Boolean co-clones
- The complexity of optimization problems
- On generating all maximal independent sets
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Generalizations of Opt P to the polynomial hierarchy
- Complete sets and the polynomial-time hierarchy
- Auditing Boolean attributes
- Optimal satisfiability for propositional calculi and constraint satisfaction problems.
- A dichotomy in the complexity of propositional circumscription
- The complexity of Boolean constraint satisfaction local search problems
- The complexity of minimal satisfiability problems
- Complexity of generalized satisfiability counting problems
- The complexity of problems for quantified constraints
- Parametrized complexity theory.
- Closed systems of functions and predicates
- Subtractive reductions and complete problems for counting complexity classes
- The Approximability of Constraint Satisfaction Problems
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- On the unique satisfiability problem
- PP is as Hard as the Polynomial-Time Hierarchy
- Undirected ST-connectivity in log-space
- Enumerating All Solutions for Constraint Satisfaction Problems
- On the Boolean Connectivity Problem for Horn Relations
- The Complexity of Enumeration and Reliability Problems
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
- The Inverse Satisfiability Problem
- Structure in Approximation Classes
- Closure properties of constraints
- On generating all solutions of generalized satisfiability problems
- STACS 2004
- Function Algebras on Finite Sets
- The complexity of satisfiability problems
- Computational Complexity of Constraint Satisfaction
- Complexity of Default Logic on Generalized Conjunctive Queries
- A Complete Classification of the Complexity of Propositional Abduction
- Mathematical Foundations of Computer Science 2005
- Mathematical Foundations of Computer Science 2005
- Partial Polymorphisms and Constraint Satisfaction Problems
- Logic for Programming, Artificial Intelligence, and Reasoning
- Theory and Applications of Satisfiability Testing
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
