4 ms·
No. 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 ha
by gweinberg 13y ago
No. 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.