Computational complexity continuum within Ising formulation of NP problems

Abstract

The advantage of unconventional computing architectures is commonly demonstrated by solving an NP-hard problem, but some instances are easier to solve than others. Here, an optimisation simplicity criterion is proposed that classifies the complexity of instances on optical or electronic neuromorphic computers.