A spiking neural algorithm for the Network Flow problem
This work addresses the problem of expanding neuromorphic hardware applications beyond machine learning and neuroscience for researchers and engineers, though it is incremental in mapping P-complete problems to such architectures.
The paper tackles the challenge of solving the P-complete Max Network Flow problem on neuromorphic hardware by proposing an interactive neuromorphic co-processor model, showing it becomes tractable and achieving energy efficiency gains when implemented on the Intel Loihi chip without sacrificing runtime.
It is currently not clear what the potential is of neuromorphic hardware beyond machine learning and neuroscience. In this project, a problem is investigated that is inherently difficult to fully implement in neuromorphic hardware by introducing a new machine model in which a conventional Turing machine and neuromorphic oracle work together to solve such types of problems. We show that the P-complete Max Network Flow problem is intractable in models where the oracle may be consulted only once (`create-and-run' model) but becomes tractable using an interactive (`neuromorphic co-processor') model of computation. More in specific we show that a logspace-constrained Turing machine with access to an interactive neuromorphic oracle with linear space, time, and energy constraints can solve Max Network Flow. A modified variant of this algorithm is implemented on the Intel Loihi chip; a neuromorphic manycore processor developed by Intel Labs. We show that by off-loading the search for augmenting paths to the neuromorphic processor we can get energy efficiency gains, while not sacrificing runtime resources. This result demonstrates how P-complete problems can be mapped on neuromorphic architectures in a theoretically and potentially practically efficient manner.