4 ms·
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
by ck113 17y ago
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.