4 ms·

This was a really quality article. I wish I saw more stuff of this quality posted on here. Definitely checking this site out more.

• tempcomment 13y ago
  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. Sources: http://www.nytimes.com/2013/05/07/science/a-glossy-science-magazine-or-living-fossil.html?_r=0 http://www.nytimes.com/2013/05/07/science/a-glossy-science-m... http://www.slate.com/articles/news_and_politics/assessment/1997/06/gods_venture_capitalist.html http://www.slate.com/articles/news_and_politics/assessment/1...
  • pja 13y ago
    The Templeton Foundation also funds a fair bit of fundamental research in theoretical physics and maths. I wouldn't write them off entirely!
  • deleted 13y ago
    [deleted]
• 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 ago
    While I think your definition is apt, I think you vastly overestimate the number of people who grasp the phrase 'brute-force search.'
    • rmc 13y ago
      People understand what "try all the possible combinations"
      • StavrosK 13y ago
        means.
    • RyanZAG 13y ago
      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.
  • 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 ago
      TSP is NP-complete, so it is most certainly in NP.
      • 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.