DIMACS TR: 94-10

A weak version of the Blum, Shub & Smale model

Author: Pascal Koiran


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