@article{Kwisthout_2026,
doi = {10.1088/2634-4386/ae2cc1},
url = {https://doi.org/10.1088/2634-4386/ae2cc1},
year = {2026},
month = {jan},
publisher = {IOP Publishing},
volume = {6},
number = {1},
pages = {014004},
author = {Kwisthout, Johan and Diehl, Arne and Donselaar, Nils},
title = {Neuromorphic complexity theory: computational models and complexity classes for spiking neural networks*},
journal = {Neuromorphic Computing and Engineering},
abstract = {The last decade has seen the rise of neuromorphic architectures based on artificial spiking neural networks (SNNs), 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 three (increasingly complex) machine models based on SNNs where—in contrast to the familiar Turing machine—information and the manipulation thereof can be co-located in the machine. Using these models, we introduce canonical problems for our machine models, define hierarchies of complexity classes, and provide some first completeness results.}
}