HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Síma, J. Articles by Orponen, P. Search for Related Content PubMed PubMed Citation Articles by Síma, J. Articles by Orponen, P.

General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results

Jií íma

sima{at}cs.cas.cz, Institute of Computer Science, Academy of Sciences of the Czech Republic, P.O. Box 5, Prague 8, Czech Republic

Pekka Orponen

orponen{at}tcs.hut.fi, Laboratory for Theoretical Computer Science, Helsinki University of Technology, P.O. Box 5400, FIN-02015 HUT, Finland

We survey and summarize the literature on the computational aspects of neural network models by presenting a detailed taxonomy of the various models according to their complexity theoretic characteristics. The criteria of classification include the architecture of the network (feedforward versus recurrent), time model (discrete versus continuous), state type (binary versus analog), weight constraints (symmetric versus asymmetric), network size (finite nets versus infinite families), and computation type (deterministic versus probabilistic), among others. The underlying results concerning the computational power and complexity issues of perceptron, radial basis function, winner-take-all, and spiking neural networks are briefly surveyed, with pointers to the relevant literature. In our survey, we focus mainly on the digital computation whose inputs and outputs are binary in nature, although their values are quite often encoded as analog neuron states. We omit the important learning issues.

This article has been cited by other articles:

				M. J. Greene and D. M. Gordon Interaction rate informs harvester ant task decisions Behav. Ecol., March 1, 2007; 18(2): 451 - 455. [Abstract] [Full Text] [PDF]

				H. Jacobsson Rule Extraction from Recurrent Neural Networks: A Taxonomy and Review Neural Comput., June 1, 2005; 17(6): 1223 - 1263. [Abstract] [Full Text] [PDF]