A weak version of the Blum, Shub and Smale model

Author

Koiran, Pascal

Author_Institution

Lab. de l´´Inf. du Parallelisme, CNRS, Lyon, France

fYear

1993

fDate

3-5 Nov 1993

Firstpage

486

Lastpage

495

Abstract

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≠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

Keywords

computational complexity; feedforward neural nets; recurrent neural nets; Blum-Shub-Smale model of computation; complexity class; divisions; feedforward nets; multiplications; polynomial time; real numbers; real traveling salesman problem; recurrent neural networks; Analog computers; Circuits; Complexity theory; Computational modeling; Electronic mail; Feedforward neural networks; Neural networks; Polynomials; Traveling salesman problems; Turing machines;

fLanguage

English

Publisher

ieee

Conference_Titel

Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on

Conference_Location

Palo Alto, CA

Print_ISBN

0-8186-4370-6

Type

conf

DOI

10.1109/SFCS.1993.366838

Filename

366838