What Makes an Optimization Problem Hard?
Author InfoWilliam G. Macready David H. Wolpert Abstract We address the question “Are some classes of combinatorial optimization problems instrinsically harder than others, without regard to the algorithm one uses, or can difficulty only be assessed relative to particular algorithms?” We provide a measure of the hardness of a particular optimization problem for a particular optimization algorithm. We then present two algorithm-independent quantities that use this measure to provide answers to our question. In the first of these we average hardness over all possible algorithms for the optimization problem at hand. We show that according to this quantitiy, there is no distinction between optimization problems, and in this sense no problems are intrinsically harder than others. For the second quantitiy, rather than average over all algorithms we consider the level of hardness of a problem (or class of problems) for the algorithm that is optimal for that problem (or class of problems). Her
