A process in constraint solving where local inference rules are applied to constraints to iteratively reduce the domains of variables by eliminating values that cannot participate in any solution under the current constraints, often as a preprocessing or during search to prune the search space.

Principle

Enforce a chosen local consistency notion (node, arc, path, k‑consistency, or specific global propagators) repeatedly: detect and remove domain values contradicted by constraints using propagation algorithms (e.g., AC‑3, AC‑4, GAC for global constraints), until a fixed point or contradiction is reached.

Demonstration

In a Sudoku CSP, arc consistency propagation removes impossible digits from the domain of each cell by considering row, column and block constraints; as domains shrink, further propagation may force singletons that propagate additional reductions, drastically pruning backtracking search.

Misapplication

Relying on local propagation to solve NP‑hard CSPs fully or applying overly aggressive filtering that is unsound (removes values that actually belong to some global solution) due to incorrect propagator implementation; or using propagation without combining it with search when propagation alone cannot decide satisfiability.

Consequence

Propagation reduces search effort by pruning infeasible value combinations, enables early detection of contradictions, supports incremental and dynamic problem solving, and interfaces well with branching heuristics; however it does not in general replace exhaustive search except in tractable classes.

Reversal

Constraint generation or relaxation (adding constraints or weakening them) inverts propagation's narrowing function: instead of pruning domains to rule out values, one may enlarge domains or add constraints to guide a search or capture dual information, trading pruning for flexibility or overapproximation.

Boundary

Applies in CSPs with finite or finitely represented domains and relies on the chosen consistency level; propagation is sound (does not eliminate all solutions) only if propagators are correct, and completeness (finding a solution without search) holds only for specific tractable problem classes or global consistency levels.

Semantic Tension

Tension occurs between propagation and encoding approaches (encode into SAT/SMT) or between local consistency and global reasoning: local propagation is cheaper but weaker than full constraint entailment, while stronger propagation (global constraints) is costlier but can capture more pruning.

Synthesis

Constraint propagation is an iterative, sound local inference mechanism that prunes variable domains according to constraints to make search feasible; combined with branching, global propagators and heuristics it forms the backbone of practical constraint programming, balancing inference cost against pruning power.