and presentations are already available, and b) they appear to be restricted to accelerated gradient methods with no clear extension to the broader theory of computational complexity.

Non-deterministic polynomial-time (NP)-hard and -complete complexity classes can be traced to seminal work by Cook in 1971 [@Cit:cook]. The broad applicability of this work was outlined in a highly influential publication by Karp [@Cit:karp]. NP-hard problems such as the traveling salesman problem (TSP) [@Cit:TSP] and lattice-based vector problems [@Cit:lattice] arise in a wide variety of applications ranging from DNA sequencing and astronomy [@Cit:TSP_book] to encryption [@Cit:lattice]. In essence, the computation of optimal solutions for these problems quickly becomes intractable with the size of the instance (unlike problems that lie in the $P$ complexity class). Note that some problems such as graph isomorphism [@Cit:GI_klus] lie in the NP complexity class but are not expected to be NP-complete or NP-hard. Over the last few years, several efficient heuristic algorithms for approximating the solutions of NP-hard problems have been developed. For example, careful implementations of the Lin-Kernighan [@Cit:LKH] and branch-and-bound [@Cit:Concorde] heuristics have been successful in computing optimal solutions of several large instances of the TSP. However, most NP-hard problems suffer from a lack of scalable 