Random Costs in Combinatorial Optimization

The random cost problem is the problem of indentifying the minimum in a list of random numbers. By definition, this problem cannot be solved faster than by exhaustive search. It is shown that a classical $\mathrm{NP}$-hard optimization problem, number partitioning, is essentially equivalent to the random cost problem. On the one hand this explains the bad performance of heuristic approaches to the number partitioning problem, but on the other hand it allows one to calculate the probability distributions of the optimum and suboptimum costs.