On the computational power and complexity of Spiking Neural Networks
This work addresses a foundational gap for researchers and engineers in neuromorphic computing, enabling formal comparisons with traditional architectures, though it is incremental as it takes first steps rather than establishing a complete theory.
The paper tackles the lack of a formal machine model and computational complexity theory for neuromorphic architectures like spiking neural networks, introducing them as a machine model with co-located information and manipulation, and provides initial results including canonical problems, complexity class hierarchies, and completeness findings.
The last decade has seen the rise of neuromorphic architectures based on artificial spiking neural networks, such as the SpiNNaker, TrueNorth, and Loihi systems. The massive parallelism and co-locating of computation and memory in these architectures potentially allows for an energy usage that is orders of magnitude lower compared to traditional Von Neumann architectures. However, to date a comparison with more traditional computational architectures (particularly with respect to energy usage) is hampered by the lack of a formal machine model and a computational complexity theory for neuromorphic computation. In this paper we take the first steps towards such a theory. We introduce spiking neural networks as a machine model where---in contrast to the familiar Turing machine---information and the manipulation thereof are co-located in the machine. We introduce canonical problems, define hierarchies of complexity classes and provide some first completeness results.