- TSP - input: 1. a graph adjacency matrix of distances 2. a budget $b$ - output: - a tour which passes through all cities & has length $\leq$ $b$ & returns to starting point, if such a tour exists - is [[NP Complete Problems |NP Complete]] - has an approximation algorithm, the [[TSP OPT Approximation Algorithm]] https://people.eecs.berkeley.edu/~vazirani/algorithms/chap8.pdf https://stackoverflow.com/questions/49837125/confusion-about-np-hard-and-np-complete-in-traveling-salesman-problems