# On the computational power and complexity of Spiking Neural Networks

arXiv: https://arxiv.org/abs/2001.08439 · HTML: https://mlsanity.com/paper/2001.08439/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2020.

## Built on by (most cited first, 3 of 3)

- [Vector Symbolic Architectures as a Computing Framework for Emerging Hardware](https://mlsanity.com/paper/2106.05268/) (2021)
- [Neuromorphic Computing is Turing-Complete](https://mlsanity.com/paper/2104.13983/) (2021)
- [Neuromorphic-based metaheuristics: A new generation of low power, low latency and small footprint optimization algorithms](https://mlsanity.com/paper/2505.16362/) (2025)

## Abstract (arXiv)

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.