Can't a neural network only ever achieve an O(1) time approximation of an NP hard problem? Unless you're using it as a heuristic inside some broader search algorithm.