The Computational Power of Discrete Hopfield Nets with Hidden Units
- 15 February 1996
- journal article
- Published by MIT Press in Neural Computation
- Vol. 8 (2), 403-415
- https://doi.org/10.1162/neco.1996.8.2.403
Abstract
We prove that polynomial size discrete Hopfield networks with hidden units compute exactly the class of Boolean functions PSPACE/poly, i.e., the same functions as are computed by polynomial space-bounded nonuniform Turing machines. As a corollary to the construction, we observe also that networks with polynomially bounded interconnection weights compute exactly the class of functions P/poly, i.e., the class computed by polynomial time-bounded nonuniform Turing machines.Keywords
This publication has 11 references indexed in Scilit:
- Optimal simulation of automata by neural netsLecture Notes in Computer Science, 1995
- Analog computation via neural networksTheoretical Computer Science, 1994
- A generalized convergence theorem for neural networksIEEE Transactions on Information Theory, 1988
- Sequential simulation of parallel iterations and applicationsTheoretical Computer Science, 1986
- Decreasing energy functions as a tool for studying threshold networksDiscrete Applied Mathematics, 1985
- Neurons with graded response have collective computational properties like those of two-state neurons.Proceedings of the National Academy of Sciences, 1984
- Transient length in sequential iteration of threshold functionsDiscrete Applied Mathematics, 1983
- On periodical behaviour in societies with symmetric influencesCombinatorica, 1983
- Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 1982
- A logical calculus of the ideas immanent in nervous activityBulletin of Mathematical Biology, 1943