What Makes an Optimization Problem Hard?

William G. Macready and David H. Wolpert

Working Papers from Santa Fe Institute

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). Here there are classes of problems that are intrinsically harder than others.

Date: 1995-05
References: View references in EconPapers View complete reference list from CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:95-05-046

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().