Very interesting. I'd love to ask a follow-up question to tease this out a bit more. Essentially, the P vs NP divide has been enormously useful in computer science as a heuristic for which problems we should spend time looking for efficient algorithms and which ones we should be happy with exponential algorithms. If P = NP, but there is no efficient algorithm for previously-only-known-to-be--NP problems, it seems like there should be something common to those problems. Why else is there this apparent stark division? For a more sophisticated view, see Aaronson's http://www.scottaaronson.com/blog/?p=1720 for his "invisible electric fence". Charles Greathouse Analyst/Programmer Case Western Reserve University On Tue, May 27, 2014 at 5:28 PM, Tom Duff <td@pixar.com> wrote:
http://www.informit.com/articles/article.aspx?p=2213858
In "Twenty Questions for Donald Knuth", Don answers questions from 19 or 20 of his colleagues. Mostly pretty interesting. In #17 he explains why he thinks P=NP. Essentially, if it weren't he thinks we'd likely have a proof by now, and the bound on the required exponent may be unimaginably large. We might never have a constructive proof and indeed may never know a bound on the exponent. (As an analogy he quotes a graph theory problem that is known to have a polynomial-time algorithm, but the algorithm is unknown because we only have a non-constructive proof of one of its prerequisites.)
-- Tom Duff. Please do not board the elevator with the robot.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun