Question: why tsp is np complete?
Answer: Why TSP Is Not NP-complete Since it's not in NP, it can't be NP-complete. In TSP you're looking for the shortest loop that goes through every city in a given set of cities. ... Since it takes exponential time to solve NP, the solution cannot be checked in polynomial time. Thus this problem is NP-hard, but not in NP.