Knuth on P v NP, god(s)

I don’t remember exactly how I got there, but reading through a short profile on Don Knuth I was glad to learn that my worldview roughly coincides.

Taking the interview for this article as a mini-instance of “All Questions Answered,” this reporter asked about the question of P versus NP. “It’s probably true that P equals NP, but we will never know why,” Knuth answered. The question has two aspects, he explained. The first: Given a computational problem, does there exist a polynomial-time algorithm for its solution? And the second: Is that algorithm knowable—that is, can we actually write it down? “What I suspect is that there is some algorithm, it’s out there, but it’s so complicated that for practical purposes, it makes no difference because nobody will ever know what it is,” he said. A suggestive example comes from the Robertson-Seymour theorem, which says that for any minor-closed family of graphs, there exists a polynomial-time algorithm to recognize whether a given graph belongs to the family. But “almost never do we know what the algorithm is.”

But just because something is hard doesn’t mean we should give up!

Also worth noting that this appears in the middle of a piece which characterizes the early 21st century mainstream North American academic position on diversity pretty well. Knuth is being praised for his contributions to diversity for giving money that allowed MathSciNet to add authors’ names typeset in their native languages instead of just transliterating to English. I am for this, but the tenor hews a little too close to the willful ignorance of claiming mathematics is a diverse and inclusive field because it is international. How eager we were to “celebrate diversity.” Oops!

Also, if your read further, it talks about Knuth’s lectures on religion and coming out as a Christian. I think all I can say about that is that I appreciate the acknowledgement that “God” is really a just a catch-all for mystery. It makes more sense to me as a metaphor though.

Leave a Reply

Your email address will not be published.