|
Zapiski Nauchnykh Seminarov POMI, 2015, Volume 436, Pages 122–135
(Mi znsl6163)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
On a class of optimization problems with no “effectively computable” solution
M. R. Gavrilovich, V. L. Kreps National Research University "Higher School of Economics", St. Petersburg Branch
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 $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.
Key words and phrases:
optimization, concentration of measure, probabilistically checkable proofs.
Received: 02.09.2015
Citation:
M. R. Gavrilovich, V. L. Kreps, “On a class of optimization problems with no “effectively computable” solution”, Representation theory, dynamical systems, combinatorial methods. Part XXV, Zap. Nauchn. Sem. POMI, 436, POMI, St. Petersburg, 2015, 122–135; J. Math. Sci. (N. Y.), 215:6 (2016), 706–714
Linking options:
https://www.mathnet.ru/eng/znsl6163 https://www.mathnet.ru/eng/znsl/v436/p122
|
Statistics & downloads: |
Abstract page: | 135 | Full-text PDF : | 36 | References: | 30 |
|