4 ms·
On the other hand, there's Scott Aaronson's "The Scientific Case for P≠NP"[1]: "So, OK, why should you believe P≠NP? Here’s why: "Because, like any other suc
by mcguire 11y ago
On the other hand, there's Scott Aaronson's "The Scientific Case for P≠NP"[1]:
"So, OK, why should you believe P≠NP? Here’s why:
"Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false."
[1] http://www.scottaaronson.com/blog/?p=1720 http://www.scottaaronson.com/blog/?p=1720
- SilasX 11y agoI think they're agreeing on the major substantive issue, that we won't reach a world where "composing a symphony is just as easy as enjoying it" -- Aaronson, because P != NP, and Knuth, because the proof of P=NP will not provide a polynomial-time algorithm for NP-complete problems.
- danbruc 11y agoThis symphony thing comes up again and again but it seems pretty silly to me. Enjoying and composing a symphony requires understanding what makes a piece of music sound good to humans, undoubtedly a nontrivial problem, but is it really hard to imagine that once that got formalized one can use this information to search the space of all possible pieces of music for beautiful symphonies in a not terrible inefficient way? I don't think so.
- deleted 11y ago[deleted]
- eru 11y agoThat's not too surprising. Most NP-hard problems are pretty tractable in practice.