On the probabilistic continuous complexity conjecture
Files
First author draft
Date
2012
DOI
Authors
Kon, Mark A.
Version
First author draft
OA Version
Citation
Mark A Kon. 2012. "On the probabilistic continuous complexity conjecture." Available at: http://arxiv.org/abs/1212.1263v1
Abstract
In this paper we prove the probabilistic continuous complexity conjecture. In continuous complexity theory, this states that the complexity of solving a continuous problem with probability approaching 1 converges (in this limit) to the complexity of solving the same problem in its worst case. We prove the conjecture holds if and only if space of problem elements is uniformly convex. The non-uniformly convex case has a striking counterexample in the problem of identifying a Brownian path in Wiener space, where it is shown that probabilistic complexity converges to only half of the worst case complexity in this limit.