On a Class of Optimization Problems with No “Efficiently Computable” Solution

Abstract

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 MAXFLS= of calculating the maximum number of consistent equations in a given overdetermined system of linear equations. A problem of this kind is faced by a decision maker (an Agent) choosing means to protect a house from natural disasters. For this class we establish the following. There is no “efficiently computable” optimal strategy of the Agent. As the size of a random instance of the optimization problem goes to infinity, the probability that the uniform mixed strategy of the Agent is ε-optimal goes to one. Moreover, there is no “efficiently computable” strategy of the Agent that is substantially better for each instance of the optimization problem. Bibliography: 13 titles.