On the probabilistic continuous complexity conjecture
Kon, Mark A.
MetadataShow full item record
First author draft
Citation (published version)Mark A Kon. 2012. "On the probabilistic continuous complexity conjecture." Available at: http://arxiv.org/abs/1212.1263v1
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.