[nopassrecover]

Verifying that length is less than K and verifying that length is the shortest possible route are two different questions. Can someone clarify how the travelling salesman problem is NP-Complete (i.e. how does it have a P verification?)

[philwelch]

There's a bit of confusion here. Saying the traveling salesman problem is NP-complete means more than simply it has a P verification. Saying the traveling salesman problem is in NP implies it has a P verification. But saying that it is NP-complete implies that, in addition to being in NP, any other NP problem can be (deterministic-polynomially) translated into it.

[ck113]

It's mostly just a technicality of the definition. NP (and P for that matter) can only contain "decision problems," i.e., problems for which the answer must be Yes or No.

So the NP formulation of the Traveling Salesman problem is "does this graph admit a route of length less than K?" For any constant K, that's an NP-complete problem.