Which Search Problems Are Random?

Abstract

The typical difficulty of various NP-hard problems varies with simple parameters describing their structure. This be-havior is largely independent of the search algorithm, but depends on the choice of problem ensemble. A given prob-lem instance belongs to many different ensembles, so ap-plying these observations to individual problems requires identifying which ensemble is most appropriate for predict-ing its search behavior, e.g., cost or solubility. To address this issue, we introduce a readily computable measure of randomness for search problems called “approximate en-tropy”. This new measure is better suited to search than other approaches, such as algorithmic complexity and in-formation entropy. Experiments with graph coloring and 3–SAT show how this measure can be applied.