Content deleted Content added
→Decision problems: fix template |
m Clean up duplicate template arguments using findargdups; fix ref error |
||
Line 28:
==Solution==
Constraint satisfaction problems on finite domains are typically solved using a form of [[Search algorithm|search]]. The most used techniques are variants of [[backtracking]], [[constraint propagation]], and [[Local search (optimization)|local search]]. These techniques are also often combined, as in the [[Very large-scale neighborhood search|VLNS]] method, and current research involves other technologies such as [[linear programming]].<ref>{{Cite
[[Backtracking]] is a recursive algorithm. It maintains a partial assignment of the variables. Initially, all variables are unassigned. At each step, a variable is chosen, and all possible values are assigned to it in turn. For each value, the consistency of the partial assignment with the constraints is checked; in case of consistency, a [[Recursion|recursive]] call is performed. When all values have been tried, the algorithm backtracks. In this basic backtracking algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned. Several variants of backtracking exist. [[Backmarking]] improves the efficiency of checking consistency. [[Backjumping]] allows saving part of the search by backtracking "more than one variable" in some cases. [[Constraint learning]] infers and saves new constraints that can be later used to avoid part of the search. [[Look-ahead (backtracking)|Look-ahead]] is also often used in backtracking to attempt to foresee the effects of choosing a variable or a value, thus sometimes determining in advance when a subproblem is satisfiable or unsatisfiable.
Line 39:
===Decision problems===
CSPs are also studied in [[computational complexity theory]] and [[finite model theory]]. An important [[dichotomy]] theorem states that for each set of relations, the set of all CSPs that can be represented using only relations chosen from that set is either in [[P (complexity)|P]] or [[NP-complete]]. CSPs thus provide one of the largest known subsets of [[NP (complexity)|NP]] which avoids [[NP-intermediate]] problems, whose existence was demonstrated by [[Ladner's theorem]] under the assumption that [[P versus NP problem|P ≠ NP]]. [[Schaefer's dichotomy theorem]] handles the case when all the available relations are [[Boolean operator (Boolean algebra)|Boolean operator]]s, that is, for ___domain size 2. Schaefer's dichotomy theorem was later generalized to a larger class of relations,<ref>{{Cite book| last1 = Bodirsky | first1 = Manuel| last2 = Pinsker | first2 = Michael| doi = 10.1145/1993636.1993724 | contribution = Schaefer's theorem for graphs | publisher= [[Association for Computing Machinery]]| title = Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11)| pages = 655–664 | year = 2011 | isbn = 978-1-4503-0691-1| arxiv = 1011.2894| bibcode = 2010arXiv1011.2894B| title-link = Symposium on Theory of Computing| s2cid = 47097319}}</ref> and a full dichotomy theorem was first conjectured as the Feder–Vardi conjecture<ref>{{Cite journal |last=Feder |first=Tomás |last2=Vardi |first2=Moshe Y.
Most classes of CSPs that are known to be tractable are those where the [[hypergraph]] of constraints has bounded [[treewidth]] (and there are no restrictions on the set of constraint relations), or where the constraints have arbitrary form but there exist essentially non-unary polymorphisms{{Clarify|date=February 2009}} of the set of constraint relations.
| |||