Neural networks and complexity theory

DOI10.1007/3-540-55808-X_5zbMath1493.68140MaRDI QIDQ5096819

Pekka Orponen

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items

Complexity of limit-cycle problems in Boolean networks, Deep limits of residual neural networks, On the computational power of discrete Hopfield nets, On the computational power of probabilistic and faulty neural networks, Optimising attractor computation in Boolean automata networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of small-depth threshold circuits
• Decreasing energy functions as a tool for studying threshold networks
• Asynchronous threshold networks
• On the complexity of loading shallow neural networks
• On characterizations of the class PSPACE/poly
• Stability and looping in connectionist models with asymmetric weights
• Majority gates vs. general weighted threshold gates
• Multilayer feedforward networks are universal approximators
• Transient length in sequential iteration of threshold functions
• Threshold circuits of bounded depth
• Theory of majority decision elements
• Parity, circuits, and the polynomial-time hierarchy
• On connectionist models
• The convergence of symmetric threshold automata
• On the Power of Threshold Circuits with Small Weights
• Cryptographic limitations on learning Boolean formulae and finite automata
• Efficient simulation of finite automata by neural nets
• Neural networks and physical systems with emergent collective computational abilities.
• A logical calculus of the ideas immanent in nervous activity
• Approximation by superpositions of a sigmoidal function