  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.
