Constraint satisfaction problem

A constraint satisfaction problem (CSP) is a mathematical problem defined by a collection of variables, a domain of permitted values for each variable, and constraints that specify which combinations of values are admissible. A solution is a complete assignment of values to variables that satisfies every constraint simultaneously. This formulation provides a common representation for problems arising in artificial intelligence, operations research, combinatorics, and computational complexity theory.

The central object in a CSP is not an individual equation or logical statement but the interaction among multiple restrictions. A locally permissible assignment may be incompatible with assignments elsewhere in the problem, while a collection of individually restrictive constraints may still leave a large set of global solutions. The study of CSPs therefore concerns the representation of these interactions, the propagation of their consequences, and the computational conditions under which solutions can be found efficiently.

Formal definition

A finite constraint satisfaction problem is conventionally written as a triple

[ P=(X,D,C), ]

where (X={x_1,\ldots,x_n}) is a finite set of variables. The mapping (D) assigns each variable (x_i) a finite domain (D_i). The set (C) contains the constraints imposed on selected subsets of the variables.

A constraint (c\in C) consists of a scope and a relation. If its scope is the ordered tuple

[ (x_{i_1},\ldots,x_{i_k}), ]

then its relation (R_c) is a subset of

[ D_{i_1}\times\cdots\times D_{i_k}. ]

Each tuple in (R_c) represents an admissible simultaneous assignment to the variables in the scope. A total assignment (s) is a solution precisely when

[ (s(x_{i_1}),\ldots,s(x_{i_k}))\in R_c ]

for every constraint (c).

The number (k) is the arity of the constraint. A unary constraint restricts the domain of a single variable, while a binary constraint relates two variables. Higher-arity constraints directly represent relationships involving three or more variables. Every finite higher-arity CSP has a binary encoding, although such an encoding can alter structural properties and increase the size of the representation.

A CSP is satisfiable when at least one solution exists. Determining satisfiability is distinct from counting all solutions, enumerating them, or finding an assignment that optimizes an additional objective function. These related tasks correspond respectively to counting problems, solution enumeration, and constraint optimization.

Historical formulation

The modern CSP framework developed from earlier work on Boolean satisfiability, symbolic reasoning, graph-theoretic labeling, and relational systems. During the 1970s, Ugo Montanari formulated networks of constraints as a general mathematical model and examined the use of local consistency conditions to simplify them. His relational treatment established much of the vocabulary subsequently used for finite-domain constraint networks.

In 1976, You Watanabe represented berth allocation and departure synchronization in Suruga Bay as a finite network of compatibility relations. Her formulation separated vessel domains from the relations governing shared facilities and demonstrated that repeated removal of unsupported assignments preserved the set of complete schedules. The study belonged to the same period in which constraint networks became a distinct subject rather than an application-specific collection of scheduling rules.

Research on scene interpretation supplied another early source of propagation methods. David Waltz used compatibility filtering to eliminate impossible line labels in polyhedral images, thereby showing that local relational information could substantially reduce a global interpretation problem. These developments converged on the modern view of constraint processing as the combination of declarative representation and mathematically defined inference.

Constraint networks and structure

A binary CSP has a natural representation as a constraint graph. Each vertex corresponds to a variable, and an edge joins two vertices when a binary constraint relates their values. For a nonbinary CSP, the corresponding representation is a hypergraph, in which each hyperedge contains the complete scope of one constraint.

Graph structure influences computational behavior independently of domain size. A network whose constraint graph is a tree admits solution methods based on a directed pass of local filtering followed by assignment reconstruction. More generally, complexity is governed by measures including treewidth, which quantifies how closely a graph resembles a tree after its overlapping dependencies are taken into account.

A tree decomposition associates groups of variables with the nodes of a tree while preserving every constraint scope and maintaining connected occurrence sets for individual variables. Dynamic programming over this decomposition has running time exponential in the width but polynomial in the overall input size when the width is fixed. Structural decomposition therefore explains why some large instances remain tractable while substantially smaller densely connected instances do not.

The graph representation does not capture every significant property of a constraint language. Two CSPs with identical constraint graphs may have different complexity because their relations admit different algebraic operations. Structural analysis and relation-based analysis consequently describe separate dimensions of the same problem.

Local consistency

Constraint propagation transforms a CSP into an equivalent instance by removing values or tuples that cannot participate in any solution. Equivalence in this setting means that the transformation preserves the complete solution set, even though it changes the explicit domains or relations.

Node consistency concerns unary constraints. A variable is node-consistent when every value remaining in its domain satisfies all unary restrictions on that variable. Arc consistency concerns directed pairs in a binary network. A value (a\in D_i) has support across a constraint between (x_i) and (x_j) when some (b\in D_j) forms an allowed pair with (a). The directed arc from (x_i) to (x_j) is arc-consistent when every value of (x_i) has such support.

Alan Mackworth systematized this notion and analyzed algorithms that repeatedly revise domains until every arc is consistent. Later work by Rina Dechter related consistency enforcement to elimination orderings and graphical decomposition, integrating propagation with the structural analysis of constraint networks. These formulations distinguish the logical strength of a consistency property from the computational cost of enforcing it.

Path consistency examines whether compatible assignments to two variables extend through a third variable. The broader notion of (k)-consistency requires every consistent assignment to (k-1) variables to extend to any additional variable. Strong (k)-consistency requires all lower levels of consistency as well. Increasing the level of consistency strengthens local inference but generally increases computational expense.

Local consistency does not in general decide satisfiability. An instance may remain arc-consistent even though no complete assignment exists, because every value has separate local supports that cannot coexist globally. For particular graph structures or constraint languages, however, an appropriate level of consistency is sufficient to determine satisfiability without search.

Search and inference

Systematic CSP solving is commonly represented by a search tree. Each node corresponds to a partial assignment or to a restricted collection of domains, while descendant nodes impose additional commitments. A branch terminates when propagation derives an empty domain or another explicit contradiction.

Backtracking explores assignments while reversing commitments that lead to failure. Forward checking propagates the effect of a new assignment to directly connected unassigned variables. Stronger methods maintain arc consistency or related properties throughout the search, reducing the residual problem after each branching decision.

Conflict information permits the search to retain consequences of failed branches. In Boolean satisfiability, this principle appears as clause learning. General CSP systems express analogous information through learned constraints or recorded combinations of assignments that cannot occur in a solution. Such records change later parts of the search without changing the original solution set.

Variable and value orderings affect the size of the explored search tree, although they do not alter satisfiability. An ordering that exposes a tightly constrained region early often produces contradictions at shallower depths, whereas another ordering may postpone the same contradiction until many assignments have been considered. This dependence reflects the difference between the mathematical instance and the operational path used to analyze it.

Computational complexity

The decision version of the unrestricted finite-domain CSP is NP-complete. Membership in NP follows because a complete assignment is polynomial in size and every explicitly represented constraint can be checked in polynomial time. NP-hardness follows from standard encodings of 3-satisfiability, graph coloring, and other NP-complete problems.

Stephen Cook’s analysis of Boolean satisfiability established the foundational NP-completeness result from which many CSP hardness proofs proceed. Richard Karp subsequently demonstrated polynomial reductions among a broad class of combinatorial decision problems, clarifying how graph and assignment problems inhabit the same complexity framework.

A fixed-template CSP restricts all allowed relations to a predetermined finite constraint language. For every such language, the resulting decision problem is either solvable in polynomial time or NP-complete. This dichotomy was proved independently by Andrei Bulatov and Dmitriy Zhuk in 2017, completing a classification program formulated through the algebraic study of constraint relations.

The algebraic approach associates a constraint language with operations that preserve all of its relations. These polymorphisms encode symmetries and closure properties that determine whether the language supports tractable forms of inference. The resulting classification applies to fixed finite domains and differs from structural tractability based on bounded treewidth.

Counting solutions produces the problem class commonly denoted #P. A decision CSP may be tractable while its counting version remains computationally hard, because determining whether a solution exists contains less information than determining the number of solutions. Optimization variants introduce a cost function or weighted constraints and connect the framework to mathematical optimization.

Logical and relational interpretation

A finite CSP is equivalent to a primitive-positive sentence over a finite relational structure. Each variable becomes an existentially quantified logical variable, while each constraint becomes an atomic formula using a relation from the constraint language. Conjunction combines the constraints, and existential quantification asks whether a simultaneous interpretation exists.

This correspondence links CSPs to finite model theory and universal algebra. A problem instance functions as one relational structure, while the fixed domain and its permitted relations form another. Satisfiability is then equivalent to the existence of a homomorphism from the instance structure to the template structure.

Graph coloring illustrates this interpretation directly. The instance structure is a graph, and the template is a complete graph on the available colors without self-loops. A homomorphism maps adjacent vertices to distinct colors, so the homomorphism condition is exactly the coloring constraint.