Technical Report Series in Neural and Computational Learning

[john@dcs.rhbnc.ac.uk]

The European Community ESPRIT Working Group in Neural and Computational 
       Learning Theory (NeuroCOLT):

---------------------------------------
NeuroCOLT Technical Report NC-TR-94-5:
---------------------------------------
A Weak Version of the Blum, Shub \& Smale Model

by Pascal Koiran

Abstract:
We propose a weak version of the Blum-Shub-Smale model of computation 
over the real numbers. In this weak model only a ``moderate" usage 
of multiplications and divisions is allowed. 
The class of boolean languages recognizable in polynomial
time is shown to be the complexity class P/poly. The main tool is a result
on the existence of small rational points in semi-algebraic sets which is
of independent interest. As an application, we generalize recent results 
of Siegelmann \& Sontag on recurrent neural networks, and of Maass 
on feedforward nets. A preliminary version of this paper was presented at
the 1993 IEEE Symposium on Foundations of Computer Science. Additional
results include:
\begin{itemize}
\item an efficient simulation of order-free real Turing machines by
probabilistic Turing machines in the full Blum-Shub-Smale model;
\item an efficient simulation of arithmetic circuits over the integers by
boolean circuits;
\item the strict inclusion of the real polynomial hierarchy in
weak exponential time.
\end{itemize}


------------------------
The Report NC-TR-94-5 can be accessed and printed as follows 

% ftp cscx.cs.rhbnc.ac.uk  (134.219.200.45)
Name: anonymous
password: your full email address
ftp> cd pub/neurocolt/tech_reports
ftp> binary
ftp> get nc-tr-94-5.ps.Z
ftp> bye
% zcat nc-tr-94-5.ps.Z | lpr -l

Uncompressed versions of the postscript files have also been left for anyone not
having an uncompress facility.

Best wishes
John Shawe-Taylor