Combinatorial search is among the hardest of common computational problems: the solution time can grow exponentially with the size of the problem [22]. Examples arise in scheduling, planning, circuit layout and machine vision, to name a few areas. Many of these examples can be viewed as constraint satisfaction problems (CSPs) [37]. Here we are given a set of n variables each of which can be assigned b possible values. The problem is to find an assignment for each variable that together satisfy some specified constraints. For instance, consider the small scheduling problem of selecting one of two periods in which to teach each of two classes that are taught by the same person. We can regard each class as a variable and its time slot as its value, i.e., here n=b=2. The constraints are that the two classes are not assigned to be at the same time.
Fundamentally, the combinatorial search problem consists of finding
those combinations of a discrete set of items that satisfy specified
requirements. The number of possible combinations to consider grows very
rapidly (e.g., exponentially or factorially) with the number of items,
leading to potentially lengthy solution times and severely limiting the
feasible size of such problems. For example, the number of possible
assignments in a constraint problem is 
, which grows exponentially with the problem size
(given by the number of variables
n).
Because of the exponentially large number of possibilities it appears the time required to solve such problems must grow exponentially, in the worst case. However for many such problems it is easy to verify a solution is in fact correct. These problems form the well-studied class of NP problems: informally we say they are hard to solve but easy to check. One well-studied instance is graph coloring, where the variables represent nodes in a graph, the values are colors for the nodes and the constraints are that each pair of nodes linked by an edge in the graph must have different colors. Another example is propositional satisfiability (SAT), where the variables take on logical values of true or false, and the assignment must satisfy a specified propositional formula involving the variables. Both these examples are instances of particularly difficult NP problems known as the class of NP-complete search problems [22].