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.)
Do 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.
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.
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.
All 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.
I agree, this article is really well written, and a lot of their content seems to be very high quality.
However, a word of caution - major funding for this magazine is provided by the Templeton Foundation, which is a right of center religious group. This magazine is very new, so it's hard to say what influence this has on their content, but it seems like a good thing to be cognizant of. After all, trust but verify.
