[math-fun] Don thinks P=NP

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.