Complexity classifications of Boolean constraint satisfaction problems

By N. Creignou, Sanjeev Khanna, Madhu Sudan. SIAM monographs on discrete mathematics and applications, 2001

440 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Classifying the Complexity of Constraints Using Finite Algebras (2005, methodology): “This technique has been widely used in the analysis of Boolean constraint satisfaction problems [11, 52], and in the analysis of temporal and spatial constraints [17, 44, 51]; it was introduced for the study of constraints over arbitrary finite sets in [27].”
Quantum machine learning: a classical perspective (2017, background): “In a constraint satisfaction problem (CSP), we are given a set of variables, a collection of constraints, and a list of possible assignments to each variable [111].”
Handbook of Satisfiability (2021, background): “Detailed proofs and extensions of the dichotomy theorem can be found, for example, in (83; 80).”
Concise finite-domain representations for PDDL planning tasks (2009, background): “solution existence is easy), counting the number of solutions is #P-complete [8].”