Review and Commentary: "Which Search Problems Are Random?"

There is a class of problems for which it can be proven that if a solution exists, the solution will be found in finite time. Many of these problems have inherent structure, which can be exploited to efficiently find a solution. For other problems, however, there may be no structure, and the most direct approach to finding a solution is an exhaustive search. Problems for which solutions may be found by exploring all possible solutions are called search problems.

If exhaustive search is the only known method for solving a problem, then one must try, on average, half of the possible solutions before finding one that works -- assuming, of course, that a solution exists. If a solution doesn't exist, however, and one is not aware of this fact, then every possible answer must be considered before concluding that the problem cannot be solved.

Consider, for example, the set of graph coloring problems. A graph is a network of nodes, with connections linking some of the nodes in the network to other nodes in the network. Given a handful of colors, you are asked to apply a color to each node so that no two connected nodes are the same color. If the graph is fully connected, i.e., all nodes are directly connected to all nodes, a valid solution requires as many colors as there are nodes. Also, we do not allow connections linking a node to itself.

Note that map coloring problems -- where one is challenged to color the countries in a map, such that no two countries sharing a border are the same color -- are just special cases of graph coloring problems. This can be readily seen by converting any map to a graph, as follows: Let each country be represented by a node. Introduce connections between any two nodes corresponding to countries that share a border. Now solve the equivalent graph problem.

Most humans can solve map coloring problems. However, when a graph problem arises whose structure is significantly more complex than 2D maps, a human is less likely to see a direct solution. Instead, he will resort to guessing, coloring the nodes semi-randomly, and backtracking when he "colors himself into a corner." If the human is resourceful, he will develop a system for tracking already-tried color combinations, so that he will not repeat previous guesses, and so that he will know when he has tried them all. If he finds a solution along the way, he will declare it and stop; but if not, he must continue until he has considered all combinations before being sure that there is no solution.

Many search problems, including all graph problems, are a subset of an even larger class of problems, called NP-hard, for which the cost of exhaustive search increases exponentially in the size of the problem. NP-hard problems are considered "intractable," because solving them quickly requires inordinate amounts of time or resources as the problem size increases. Unfortunately, NP-hard search problems arise frequently in everyday life, and we need mechanisms for identifying the structure in them when they occur. These mechanisms will allow us to devise sensible search heuristics, rather than resorting to undirected, random searches.