3 ms·
TSP is NP-complete, so it is most certainly in NP.
by mayank 13y ago
TSP is NP-complete, so it is most certainly in NP.
- gweinberg 13y agoNo. The traveling salesman decision problem (is there a circuit of length m) is NP complete. The traveling salesman problem (what is the shortest circuit) is harder. This has been discussed on HN before.
- mayank 13y agoAll NP problems are decision problems. When you say "x is in NP", you're implicitly referring to the decision problem. NP-hard does not mean "harder than NP", although that is its colloquial interpretation.