ML Anthology

The Computational Power of Discrete Hopfield Nets with Hidden Units

Pekka Orponen
NeCo 1996 pp. 403-415
doi:10.1162/NECO.1996.8.2.403 /neco/1996/orponen1996neco-computational/

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.

PDF NeCo Semantic Scholar

Cite

Text

Orponen. "The Computational Power of Discrete Hopfield Nets with Hidden Units." Neural Computation, 1996. doi:10.1162/NECO.1996.8.2.403

Markdown

[Orponen. "The Computational Power of Discrete Hopfield Nets with Hidden Units." Neural Computation, 1996.](https://mlanthology.org/neco/1996/orponen1996neco-computational/) doi:10.1162/NECO.1996.8.2.403

BibTeX

@article{orponen1996neco-computational,
  title     = {{The Computational Power of Discrete Hopfield Nets with Hidden Units}},
  author    = {Orponen, Pekka},
  journal   = {Neural Computation},
  year      = {1996},
  pages     = {403-415},
  doi       = {10.1162/NECO.1996.8.2.403},
  volume    = {8},
  url       = {https://mlanthology.org/neco/1996/orponen1996neco-computational/}
}