General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
Open accessThe DOI matches its Crossref record; 10 of the 10 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Learning representations by back-propagating errors
Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986) · Nature · doi:10.1038/323533a0 · Cited by 31,892
Neural networks and physical systems with emergent collective computational abilities.
Hopfield, J. J. (1982) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.79.8.2554 · Cited by 19,270
The perceptron: A probabilistic model for information storage and organization in the brain.
Rosenblatt, F. (1958) · Psychological Review · doi:10.1037/h0042519 · Cited by 12,280
Hopfield, J. J. (1984) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.81.10.3088 · Cited by 6,918
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · cited 1×
“…algorithm that solves the MIN ENERGY problem to within an absolute error of less than 0.243W in binary Hopfield nets of weight W can be implemented (Šı́ma et al., 2000), based on a high-performance approximate algorithm for the MAX CUT problem (Goemans & Williamson, 1995; Mahajan & Ramesh, 1999).”
MethodA learning algorithm for Boltzmann machines
Ackley, D. H., Hinton, G. E., & Sejnowski, T. J. (1985) · Cognitive Science · doi:10.1207/s15516709cog0901_7 · Cited by 3,402
Cover, T. M. (1965) · IEEE Transactions on Electronic Computers · doi:10.1109/pgec.1965.264137 · Cited by 2,044
Threshold circuits of bounded depth
Hajnal, A., Maass, W., Pudlák, P., Szegedy, M., & Turán, G. (1993) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(93)90001-d · Cited by 237
Analytic theory of the ground state properties of a spin glass. I. Ising spin glass
Tanaka, F., & Edwards, S. F. (1980) · Journal of Physics F: Metal Physics · doi:10.1088/0305-4608/10/12/017 · Cited by 127
Computational Work and Time on Finite Machines
Savage, J. E. (1972) · Journal of the ACM · doi:10.1145/321724.321731 · Cited by 105
Cited by
Fitch, W. T. (2010) · doi:10.1017/cbo9780511817779 · Cited by 594
Multivariate data analysis applied to spectroscopy: Potential application to juice and fruit quality
Cozzolino, D., Cynkar, W. U., Shah, N., & Smith, P. (2011) · Food Research International · doi:10.1016/j.foodres.2011.01.041 · Cited by 227
Fitch, W. T. (2014) · Physics of Life Reviews · doi:10.1016/j.plrev.2014.04.005 · Cited by 223
“Thus, the re-marriage of rules and statistics, and nature via nurture, is a revolution ready to occur.”
Background
Metadata
- Authors
- Šíma, J., & Orponen, P.
- Venue
- Neural Computation
- Publisher
- MIT Press
- Published
- 2003-12-01
- Volume
- 15
- Issue
- 12
- Pages
- 2727-2778
- ISSN
- 0899-7667 (ISSN-L)
- 1530-888X
- OpenAlex
- W2148888011
- Cited by
- 185
- References
- 10
- FWCI
- 9.89
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.