Complexity classes: P, NP, NP-complete
Theory of Computation · Engineering
Study notes
Verify a TSP tour of length <= K: given the tour order, sum the edges and compare: O(n). So TSP-decision is in NP (easy to verify). Finding the tour seems to need exponential search. If anyone finds a polynomial TSP solver, P = NP and every NP problem falls. No one has, in 50 years.