3 ms·
This is just wrong. Roughly speaking, P is the set of problems that are easy to solve. NP is the set of problems for which it is easy to verify that a solution
by gweinberg 13y ago
This is just wrong. Roughly speaking, P is the set of problems that are easy to solve. NP is the set of problems for which it is easy to verify that a solution is correct. There are problems which can be solved by brute force but which are not in NP.
For example, the traveling salesman problem.
- mayank 13y agoTSP 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.