On a class of optimization problems with no ``effectively computable'' solution

M. R. Gavrilovich ; V. L. Kreps

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXV, Tome 436 (2015), pp. 122-135

Résumé

It is well known that large random structures may have nonrandom macroscopic properties. We give an example of nonrandom properties for a class of large optimization problems related to the computational problem $MAX\,FLS^=$ of calculating the maximum number of consistent equations in a given overdetermined system of linear equations. For this class we establish the following. There is no “efficiently computable” optimal strategy. When the size of a random instance of the optimization problem goes to infinity, the probability that the uniform mixed strategy is $\varepsilon$-optimal goes to one. Moreover, there is no “efficiently computable” strategy that is substantially better for each instance of the optimization problem.