Re:Throwing some light on NP-completeness and the P=NP problem
by nopassrecover on Wednesday June 03, 2009 @06:12PM
(#640558)
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?)
[ Parent
| on HN ]
Re:Throwing some light on NP-completeness and the P=NP problem
by philwelch on Wednesday June 03, 2009 @06:26PM
(#640589)
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.
Re:Throwing some light on NP-completeness and the P=NP problem
by ck113 on Wednesday June 03, 2009 @06:28PM
(#640592)
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.