## Lunch with Donald Knuth

Posted on October 31, 2018 in Experiences

On Halloween, Donald E. Knuth (wiki) visited the University of Waterloo for a distinguished lecture, and thanks to my advisor Prof. Jeff Shallit, who arranged a lunch with him for a smaller group of people, which is how I could meet him in person. My first thought when he appeared was ‘he is quite taller than he looks in the photos’.

Whenever Knuth gives a talk, almost all of it is interactive and Q/A based. He takes all kinds of questions (except politics and religion) from the audience. I could only appreciate all the wisdom his answers had. Almost every opinion was accompanied by an anecdote from his own life experience. Here’s a set of things that were brought up during the lunch and the talk (unfortunately, I forgot most of the conversations).
The public talk is now available on youtube.

#### On P vs NP

Knuth believes that P = NP. This obviously needs an explanation, and I will try to present the reason based on my understanding of his argument. First let’s be clear on what it means when we say P = NP. It means that there exists an integer $k$ and an algorithm $A$ which solves every problem in the class NP of size $m$ bits in $m^k$ elementary steps. Now Knuth has two points:

• Imagine a number $k$ which is finite but excessively humongous (to have a sense of humongous numbers, one might look at Ackermann Function or even Graham’s Number). But irrespective of how big a finite number is, it is always 0% as big as infinity. Now there exist an incredibly huge number of algorithms that do $m^k$ elementary operations on the $m$ bits and it is extremely hard to believe that none of those algorithms can do what we want.
• The resolution of the P vs NP problem will not be a helpful result because the proof almost certainly will be non-constructive. Mathematics has a lot of examples where we have proof for the existence of something, but that proof does not help us find the actual thing (I’m thinking cryptography here). So proving the existence of $A$ is different from actually finding $A$.