Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Operations and polynomials in algebraic structures, primal algebras (08A40)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
The complexity of optimization problems
The complexity of computing the permanent
Parametrized complexity theory.
Complexity classifications of Boolean constraint satisfaction problems
The Complexity of Enumeration and Reliability Problems
Closure properties of constraints
Function Algebras on Finite Sets
The complexity of satisfiability problems
Structure in Approximation Classes
On generating all solutions of generalized satisfiability problems
Parameterized complexity of constraint satisfaction problems
Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
The complexity of Boolean constraint satisfaction local search problems
Complexity of generalized satisfiability counting problems
Closed systems of functions and predicates
Subtractive reductions and complete problems for counting complexity classes
Structure identification of Boolean relations and plain bases for co-clones
On generating all maximal independent sets
The Inverse Satisfiability Problem
A dichotomy theorem for maximum generalized satisfiability problems.
PP is as Hard as the Polynomial-Time Hierarchy
The approximability of constraint satisfaction problems
Mathematical Foundations of Computer Science 2005
Undirected ST-connectivity in log-space
Theory and Applications of Satisfiability Testing
Auditing Boolean attributes
Enumerating All Solutions for Constraint Satisfaction Problems
Complete sets and the polynomial-time hierarchy
#P-COMPLETENESS VIA MANY-ONE REDUCTIONS
The complexity of minimal satisfiability problems
Logic for Programming, Artificial Intelligence, and Reasoning
Partial Polymorphisms and Constraint Satisfaction Problems
A Complete Classification of the Complexity of Propositional Abduction
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
On the unique satisfiability problem
Bases for Boolean co-clones
A dichotomy in the complexity of propositional circumscription
STACS 2004
Recognizing frozen variables in constraint satisfaction problems
Complexity of Default Logic on Generalized Conjunctive Queries
Generalizations of Opt P to the polynomial hierarchy
The complexity of problems for quantified constraints
Optimal satisfiability for propositional calculi and constraint satisfaction problems.
On the Boolean Connectivity Problem for Horn Relations
Computational Complexity of Constraint Satisfaction
Mathematical Foundations of Computer Science 2005

Cited In (14)

Non-local configuration of component interfaces by constraint satisfaction
Minimal distance of propositional models
A Dichotomy Theorem for the Inverse Satisfiability Problem
Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
Title not available (Why is that?)
Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight
The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
Complexity Classifications for Logic-Based Argumentation
Paradigms for parameterized enumeration
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework

This page was built for publication: Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5504698)