Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
type: Item
instance of: scholarly article
title: Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
zbMATH Open document ID: 1171.68495
DOI: 10.1007/978-3-540-92800-3_2
author: Nadia Creignou
author: Heribert Vollmer
published in: Complexity of Constraints
publication date: 2009-01-22T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 08A40
zbMATH DE Number: 5496762
MaRDI profile type: MaRDI publication profile
full work available at URL: 978-3-540-92800-3 2
OpenAlex ID: W1554715854
cites work: Mathematical Foundations of Computer Science 2005
cites work: The complexity of problems for quantified constraints
cites work: Theory and Applications of Satisfiability Testing
cites work: On the unique satisfiability problem
cites work: Q4411838
cites work: STACS 2004
cites work: Bases for Boolean co-clones
cites work: The complexity of Boolean constraint satisfaction local search problems
cites work: Complexity of generalized satisfiability counting problems
cites work: On generating all solutions of generalized satisfiability problems
cites work: Complexity of Default Logic on Generalized Conjunctive Queries
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Structure in Approximation Classes
cites work: Structure identification of Boolean relations and plain bases for co-clones
cites work: A dichotomy theorem for maximum generalized satisfiability problems.
cites work: A Complete Classification of the Complexity of Propositional Abduction
cites work: Subtractive reductions and complete problems for counting complexity classes
cites work: Parametrized complexity theory.
cites work: Closed systems of functions and predicates
cites work: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
cites work: Closure properties of constraints
cites work: Recognizing frozen variables in constraint satisfaction problems
cites work: On generating all maximal independent sets
cites work: Q4934341
cites work: The complexity of minimal satisfiability problems
cites work: A dichotomy in the complexity of propositional circumscription
cites work: Q4488342
cites work: Auditing Boolean attributes
cites work: The complexity of optimization problems
cites work: Generalizations of Opt P to the polynomial hierarchy
cites work: The Inverse Satisfiability Problem
cites work: Q4273947
cites work: The approximability of constraint satisfaction problems
cites work: Q4526965
cites work: Function Algebras on Finite Sets
cites work: Parameterized complexity of constraint satisfaction problems
cites work: On the Boolean Connectivity Problem for Horn Relations
cites work: Logic for Programming, Artificial Intelligence, and Reasoning
cites work: Q4298260
cites work: Q4354427
cites work: Undirected ST-connectivity in log-space
cites work: Optimal satisfiability for propositional calculi and constraint satisfaction problems.
cites work: The complexity of satisfiability problems
cites work: Enumerating All Solutions for Constraint Satisfaction Problems
cites work: Q4131648
cites work: Partial Polymorphisms and Constraint Satisfaction Problems
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Computational Complexity of Constraint Satisfaction
cites work: Complete sets and the polynomial-time hierarchy
cites work: #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
Recommended article: The complexity of satisfiability problems
Recommended article: Complexity of satisfiability problems with symmetric polynomial clauses
Recommended article: Computational Complexity of Constraint Satisfaction
Recommended article: Parameterized complexity of constraint satisfaction problems
Recommended article: A simplified NP-complete satisfiability problem
description: scientific article; zbMATH DE number 5496762