Complexity classifications of Boolean constraint satisfaction problems

DOI10.1137/1.9780898718546MaRDI QIDQ2723175zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Sanjeev Khanna, Madhu Sudan

Publication date 3 July 2001

Published in SIAM Monographs on Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9780898718546

zbMATH Keywords

complexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Review text

Complexity theory deals with infinitely many complexity classes, infinitely many questions, and innumerable possible resolutions to these questions. This powerful feature has a severely limiting factor in its scope. It limits the ability to present results compactly. This monograph attempts to break free of these inherent barriers in the study of complexity theory by restricting its attention to a microcosmos of computational problems, Boolean constraint satisfaction problems. This restricted class of problems continues to exhibit much of the natural diversity of computational problems without exhibiting the corresponding limitations. In particular, the Boolean constraint version of the complexity classes known from general complexity theory can be defined. These classes continue to have a rich collection of complete problems. They continue to have infinitely many different problems. However, it turns out that it is possible to completely classify the complexity of all the problems of these classes -- one of the book's goals is to present results of the form ``If all constraints in a given set \(F\) of templates satisfy a certain property \(P\), then a canonical algorithm can be applied to solve the corresponding constraint satisfaction problem efficiently; the absence of the property \(P\) says that solving the constraint satisfaction problem associated with \(F\) is hard. By focusing on this restricted world, it is possible to present a reasonably accurate bird's eye view of complexity theory. The book is written for researchers in optimization and computer science who spend a good deal of their time analyzing new computational problems. Furthermore, the book is as self-contained as possible and could be followed by any student who has taken the first course on the theory of computation.

Recommendations

• Computational Complexity of Constraint Satisfaction
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Methods and Applications of Artificial Intelligence
• Tractability in constraint satisfaction problems: a survey
• Classifying the Complexity of Constraints Using Finite Algebras

Cited in

(only showing first 100 items - show all)

• Existentially restricted quantified constraint satisfaction
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Minimization of locally defined submodular functions by optimal soft arc consistency
• Relatively quantified constraint satisfaction
• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• Bases for Boolean co-clones
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Optimal satisfiability for propositional calculi and constraint satisfaction problems.
• Towards a characterization of constant-factor approximable finite-valued CSPs
• Temporal network optimization subject to connectivity constraints
• Colocating tasks in data centers using a side-effects performance model
• The complexity of Boolean constraint satisfaction local search problems
• The complexity of minimal satisfiability problems
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Low-level dichotomy for quantified constraint satisfaction problems
• The complexity of problems for quantified constraints
• Dichotomy for Holant\(^\ast\) problems on the Boolean domain
• Multiaffine polynomials over a finite field
• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Combinatorial method for solving systems of linear constraints
• Isomorphic implication
• On the computation of the Möbius transform
• Minimal distance of propositional models
• Supermodular functions and the complexity of MAX CSP
• Solving quantified constraint satisfaction problems
• On planar valued CSPs
• Paradigms for parameterized enumeration
• Majority constraints have bounded pathwidth duality
• A complete 4-parametric complexity classification of short shop scheduling problems
• Search techniques for SAT-based Boolean optimization
• Predecessor existence problems for finite discrete dynamical systems
• The complexity of soft constraint satisfaction
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Complexity of clausal constraints over chains
• A dichotomy for real weighted Holant problems
• Bridging constraint satisfaction and Boolean satisfiability
• Universal qudit Hamiltonians
• Multiaffinity testing of Boolean functions using their Zhegalkin polynomials
• Complexity classification of local Hamiltonian problems
• As Close as It Gets
• A complete dichotomy rises from the capture of vanishing signatures
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
• Complexity Classifications for Logic-Based Argumentation
• Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations
• On the complexity of the model checking problem
• A Dichotomy Theorem for Polynomial Evaluation
• The Expressive Power of Binary Submodular Functions
• Complexity of infinite-domain constraint satisfaction
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Necessary conditions for tractability of valued CSPs
• First-Order Model Checking Problems Parameterized by the Model
• Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
• The Expressive Power of Valued Constraints: Hierarchies and Collapses
• Modularity-based decompositions for valued CSP
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• The complexity of complex weighted Boolean \#CSP
• On the approximability and hardness of minimum topic connected overlay and its special instances
• The complexity of surjective homomorphism problems-a survey
• Quantum machine learning: a classical perspective
• Colouring, constraint satisfaction, and complexity
• Complexity Dichotomies for Counting Problems
• An algebraic hardness criterion for surjective constraint satisfaction.
• Boolean max-co-clones
• On the Complexity of Holant Problems
• The complexity of valued CSPs
• Quantified Constraints in Twenty Seventeen
• Improved Computational Approaches and Heuristics for Zero Forcing
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• On the strength of uniqueness quantification in primitive positive formulas
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• The complexity of quantified constraints using the algebraic formulation
• Schaefer classes, Post classes and Galois connections
• Стабилизаторы некоторых семейств булевых функций, образующих Галуа-замкнутые подалгебры алгебры Шефера
• Tractability of quantified temporal constraints to the max
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Constraint satisfaction problems for reducts of homogeneous graphs
• The power of linear programming for general-valued CSPs
• The complexity of general-valued CSPs
• STACS 2004
• Classification of a Class of Counting Problems Using Holographic Reductions
• A computational proof of complexity of some restricted counting problems
• The power of Sherali-Adams relaxations for general-valued CSPs
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Learnability of solutions to conjunctive queries
• Quantified constraint satisfaction and the polynomially generated powers property
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Basics of Galois Connections
• Dualities for Constraint Satisfaction Problems
• Introduction to the Maximum Solution Problem
• The next whisky bar
• The complexity of conservative valued CSPs
• A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
• Optimal polynomial-time compression for Boolean Max CSP
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• Parameterized complexity and kernelizability of max ones and exact ones problems

Describes a project that uses

Uses Software

• Ltur

This page was built for publication: Complexity classifications of Boolean constraint satisfaction problems

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