NeuroCOLT

Neural Networks and Computational Learning Theory

About NeuroCOLT

Papers Archive

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-94-010

Computational Complexity of Neural Networks: a Survey

PEKKA ORPONEN
Department of Computer Science
P. O. Box 26
FIN-00014 University of Helsinki
Finland

Abstract
We survey some of the central results in the complexity theory of discrete neural networks, with pointers to the literature.  Our main emphasis is on the computational power of various acyclic and cyclic network models, but we also discuss briefly the complexity aspects of synthesizing networks from examples of their behavior.

Download Compressed Postscript