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

"NP-hard," "search problems," "algorithmic complexity," and "approximate entropy" are difficult concepts for the average person to grasp. However, most will have little difficulty understanding that being able to evaluate the cost of solving a class of problems is useful in the field of artificial intelligence. The more that is known about a search problem, the more prepared AI researchers can be to devise solution strategies -- strategies that are better than exhaustive search and more effective on a greater percentage of problems encountered in everyday life.

Many AI systems address search problems based on the ensemble to which they belong. The ApEn measure, however, focuses on the internal structure of the problem itself, making it possible to characterize the problem without identifying any particular ensemble. This allows us to generate predictions about search behavior without actually understanding the processes from which the problem originates. This is a breakthrough because, for many problems we encounter, determining those processes is impossible.

In his evaluation of ApEn, Hogg raises an issue that has appeared time and time again in our class discussions and textbook reading: the importance of finding a good problem representation. (Hogg shows in his paper that ApEn fails to discriminate structured search problems from random search problems when bad representations are used.) I have proposed in my online journals for this course that if anyone ever proves P == NP, it will be because he has found a really good representation for an NP-hard problem. Perhaps all search problems, no matter how random they appear at first, have some sort of structure, and ApEn is simply a measure of how close one is to finding it.

A major unsolved problem [in computer science] is the so-called P=NP problem: machines are considered in which there is a certain amount of freedom in choosing the next step in a computation (such machines are called non-deterministic). By making good guesses (or choices) one can often obtain a quicker computation than by systematically working through all possible cases in a deterministic way. The P == NP problem asks whether every function computable on a non-deterministic machine in polynomial [i.e., tractable] time is computable in polynomial time on ordinary (deterministic) machines.

N. J. Cutland, Computability. Cambridge University Press, 1980. p. 238.