On real Turing machines that toss coins
Felipe Cucker, Marek Karpiński, Pascal Koiran, Thomas Lickteig, Kai Werther · 1995
In this paper we consider real counterparts of classical probabilistic complexity classes in the framework of real Turing machines as introduced by Blum, Shub, and Smale [2].We give an extension of the well-known "BPP ~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 lR~.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.