NeuroCOLT: Neural Networks and Computational Learning Theory

NeuroCOLT

Neural Networks and Computational Learning Theory

1994	1995
1996	1997
1998	1999
2000	2001

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-94-005

A Weak Version of the Blum, Shub & Smale Model

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 the real polynomial hierarchy in weak exponential time.

Download Compressed Postscript