4 ms·
The only problem is MIT's news office; "roughly speaking, P is a set of relatively easy problems, NP is a set of incredibly hard problems, and if they’re equal,
by drostie 13y ago
The only problem is MIT's news office; "roughly speaking, P is a set of relatively easy problems, NP is a set of incredibly hard problems, and if they’re equal, then a large number of computer science problems that seem to be incredibly hard are actually relatively easy." (It's wrong first because P ⊆ NP and second because it doesn't tell you what's really at stake here.)
I think you could instead say "Roughly speaking, P is a set of easy-looking problems, while NP is a set of problems which can be solved the hard way, by a brute-force search. If they're equal, then every brute-force-able problem is hiding some much easier solution." You could also add a sentence like, "Most computer scientists believe that this is wrong -- that sometimes you can't really improve on a brute-force search. But nobody knows how to prove that negative, it seems to require understanding everything which computers can possibly do."
In one paragraph you can explain the gist of P = NP, I think, to a lay audience. I guess many of them might not know what a brute-force solution is, but you might replace it above with "trying all the combinations" or so. (Hat tip to Scott Aaronson for an essential element of this explanation.)
- jmduke 13y agoWhile I think your definition is apt, I think you vastly overestimate the number of people who grasp the phrase 'brute-force search.'
- rmc 13y agoPeople understand what "try all the possible combinations"
- StavrosK 13y agomeans.
- RyanZAG 13y agoDo we really have to be vastly overestimating this stuff? What happens if we use the phrase 'brute-force search' and people go look up what it means? Seems like a net-positive to me. If we reduce everything for the lowest common denominator, then pretty soon nobody has any reason to raise themselves above that.
- gweinberg 13y agoThis 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.