{"id":325,"date":"2022-01-08T21:55:57","date_gmt":"2022-01-08T21:55:57","guid":{"rendered":"https:\/\/mathlab.io\/?p=325"},"modified":"2022-01-09T17:09:23","modified_gmt":"2022-01-09T17:09:23","slug":"knuth-on-p-v-np-gods","status":"publish","type":"post","link":"https:\/\/automathon.org\/index.php\/2022\/01\/08\/knuth-on-p-v-np-gods\/","title":{"rendered":"Knuth on P v NP, god(s)"},"content":{"rendered":"\n

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

Taking the interview for this article as a mini-instance of \u201cAll Questions Answered,\u201d this reporter asked about the question of P versus NP. \u201cIt\u2019s probably true that P equals NP, but we will never know why,\u201d 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\u2014that is, can we actually write it down? \u201cWhat I suspect is that there is some algorithm, it\u2019s out there, but it\u2019s so complicated that for practical purposes, it makes no difference because nobody will ever know what it is,\u201d 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 \u201calmost never do we know what the algorithm is.\u201d<\/p><\/blockquote>\n\n\n\n

But just because something is hard doesn’t mean we should give up!<\/p>\n\n\n\n

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! <\/p>\n\n\n\n

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.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 \u201cAll Questions Answered,\u201d this reporter asked about the question of P versus NP. \u201cIt\u2019s probably true that PRead more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[11,1],"tags":[31,32],"class_list":["post-325","post","type-post","status-publish","format-standard","hentry","category-complexity","category-uncategorized","tag-ams","tag-knuth"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/posts\/325","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/comments?post=325"}],"version-history":[{"count":4,"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/posts\/325\/revisions"}],"predecessor-version":[{"id":346,"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/posts\/325\/revisions\/346"}],"wp:attachment":[{"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/media?parent=325"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/categories?post=325"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/automathon.org\/index.php\/wp-json\/wp\/v2\/tags?post=325"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}