A weak version of the Blum, Shub and Smale model
Pascal Koiran · 2002
We propose a weak version of the Blum-Shub-Smale model (1989) of computation over the real numbers. In this weak model only a "moderate" usage of multiplications and divisions is allowed. The class of languages recognizable in polynomial time as shown to be the complexity class P/poly. This implies under a standard complexity-theoretic assumption that P/spl ne/NP in the weak model, and that problems such as the real traveling salesman problem cannot be solved in polynomial time. As an application, we generalize recent results of H.T. Siegelmann and E.D. Sontag (1993) on recurrent neural networks, and of W. Maass (1993) on feedforward nets.>