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].

Wed Mar 20 16:29:17 PST 1996