On Real Turing Machines that Toss Coins

Dr. Felipe Cucker, ICSI

In this talk we consider real counterparts of classical probabilistic complexity classes in the framework of real Turing machines as introduced by Blum, Shub, and Smale. We give an extension of the well-known $\BPP \subseteq \P/\poly$ result from discrete complexity theory to a very general setting in the real number model. This result holds for real inputs, real outputs and random elements drawn from an arbitrary probability distribution over $\R^m$. Then we turn to the study of Boolean parts, that is, classes of languages of zero-one vectors accepted by real machines. In particular we show that the classes $\BPP$, $\PP$, $\PH$, and $\PSPACE$ are not enlarged by allowing the use of real constants and arithmetic at unit cost provided we restrict branching to equality tests.