|
NeuroCOLT
Technical Report NC-TR-95-018
On real Turing
machines that toss coins
Felipe
Cucker
Universitat Pompeu Fabra
Marek
Karpinski
Universitaet Bonn
Pascal
Koiran
DIMACS, Rutgers University
Thomas
Lickteig
Universitaet Bonn
Kai
Werther
Universitaet Bonn
Abstract
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 \cite{BSS}. 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.
Download Compressed
Postscript
|