DIMACS TR: 94-10
A weak version of the Blum, Shub & Smale model
Author: 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:
- an efficient simulation of order-free real Turing machines by
probabilistic Turing machines in the full Blum-Shub-Smale model;
- an efficient simulation of arithmetic circuits over the integers by
boolean circuits;
- the strict inclusion of non-deterministic full polynomial time in
weak exponential time.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-10.ps
DIMACS Home Page