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

DOI10.1007/978-3-540-92800-3_2MaRDI QIDQ5504698zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Heribert Vollmer

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

Mathematics Subject Classification ID

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

Recommendations

• The complexity of satisfiability problems
• Complexity of satisfiability problems with symmetric polynomial clauses
• Computational Complexity of Constraint Satisfaction
• Parameterized complexity of constraint satisfaction problems
• A simplified NP-complete satisfiability problem

Cites work

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

Cited in

(17)

• 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
• Minimal distance of propositional models
• Paradigms for parameterized enumeration
• Complexity Classifications for Logic-Based Argumentation
• Enumerating all solutions of a Boolean CSP by non-decreasing weight
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• On the applicability of Post's lattice
• scientific article; zbMATH DE number 6970794 (Why is no real title available?)
• scientific article; zbMATH DE number 1390075 (Why is no real title available?)
• On the strength of uniqueness quantification in primitive positive formulas
• A dichotomy theorem for the inverse satisfiability problem
• A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
• Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework
• Functional completeness and primitive positive decomposition of relations on finite domains
• On when the union of two algebraic sets is algebraic
• Non-local configuration of component interfaces by constraint satisfaction

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)