News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.