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

Artificial intelligence systems often require solutions to NP-hard search problems. If these problems were simply a random selection from the set of all NP-hard problems, many AI systems could never achieve viability. Fortunately, life is not random, and neither are the situations from which these problems arise, so many of the NP-hard searches that must be performed in practical applications have inherent structure which can be exploited. Recognizing this structure is the key to choosing a suitable strategy for solving the problem in reasonable time. At all costs, we would like to avoid brute-force solution searching.

Search problems can often be classified by their internal structure, or by the source or situation from which they arise. These groups are called search ensembles. For example, the subset of graph coloring problems corresponding to conceivable 2D geographic maps have structural features in common, and can be called an ensemble.

The success of many AI systems depends on the designer's ability to characterize and evaluate the complexity of search ensembles that the system is likely to face. Many techniques have been proposed to do this. For example, many researchers have proposed representing an ensemble with a program that can generate it, and then measuring that program's algorithmic complexity, as one way to characterize an ensemble. Hogg rejects this idea with evidence that it is possible for a search problem to be a member of more than one ensemble.

Hogg favors a practical measure of search problem complexity called "approximate entropy," or ApEn. Roughly put, ApEn measures the probability that two components of a single search problem will be identical if they contain smaller components that also are identical. The main objective of Hogg's paper is to demonstrate how ApEn can be applied to certain classical search problems, and to demonstrate the effectiveness of ApEn in distinguishing random (chaotic) ensembles from ensembles that have some sort of order. Hogg quantifies the results of his experiments with several dramatic graphs, which convincingly illustrate that ApEn is indeed useful for characterizing search ensembles, and hence also useful for predicting an ensemble's search behavior.