|
NeuroCOLT
Technical Report NC-TR-94-007
On
the power of real Turing machines over binary inputs
Felipe
Cucker,
Universitat Pompeu Fabra,
Balmes 132, Barcelona 08008, SPAIN
&
Dima Grigoriev,
Depts. of Comp. Science and Maths,
Penn State University,
University Park, PA 16802, USA
Abstract
In recent years the study of the complexity of computational problems
involving real numbers has been an increasing research area. Blum,
Shub and Smale (1989) proposed a computational model ---the real Turing
machine--- for dealing with the above problems was developed.
The aim of this paper is to prove that $\BP(\PAR)=\;$PSPACE/{\it poly}
where $\PAR$ is the class of sets computed in parallel polynomial
time by (ordinary) real Turing machines. As a consequence we
obtain the existence of binary sets that do not belong to the Boolean
part of $\PAR$ (an extension of the result of Koiran (1994) since
$\PH\subseteq\PAR$) and a separation of complexity classes in the
real setting.
Download Compressed Postscript
|