Transcript of a Lex Fridman interview with Donald Knuth focusing on the P vs NP question. Knuth explains his intuition that P may equal NP but that a proof (even constructive) might not yield practically usable algorithms because the space of possible algorithms is astronomically large. He gives examples: the game of Hex (a finite perfect-information game with a provable winning strategy but no practical constructive algorithm known) and the Robertson–Seymour graph-minors theorem (which guarantees a finite obstruction set and thus a polynomial-time decision algorithm in principle, yet the explicit obstructions — and hence the concrete algorithm — may be unknown). Knuth frames his view probabilistically (many possible algorithms exist by coincidence), and Lex draws an analogy to the search for extraterrestrial life.
Chapters
You've mentioned over the past few years that you believe P may be equal to np, but that it's not really. You know, if somebody does prove that P equals np, it will not directly lead to an actual algorithm to solve difficult problems. Can you explain your intuition here? Has it been changed and in general, on the difference between easy and difficult problems of P&NP and so on?
Yeah. So the popular idea is if an algorithm exists, then somebody will find it and it's just a matter of writing it down. But many more algorithms exist than anybody can understand or ever make use of or discover. Yeah. Because they're just way beyond human comprehension. The total number of algorithms is more than mind boggling. So we have situations now where we know that algorithms exist, but we don't know. We don't have the foggiest idea what the algorithms are. There are simple examples based on game playing where you have, where you say, well, there must be an algorithm that exists to win in the game of Hex for the first player to win in the game of Hex, because hex is always either a win for the first player or the second player.
Well, what's the game of hex?
There's a game of hex which is which based on putting Pebbles onto a hexagonal board. And the white player tries to get a white path from left to right and the black player tries to get a black path from bottom to top.
And how does capture occur? Just so.
And there's no capture. You just put Pebbles down one at a time. But there's no draws because after all the white and black are played, there's either going to be a white path across from each to west or a black path from, from bottom to top. So there's always, you know, it's a perfect information game. And people, people take turns like, like Tic tac toe and board can be different sizes, but there's no possibility of a draw. And players move one at a time. And so it's got to be either a first player win or a second player win. Mathematically, you follow out all the trees and either there's always a win for the first player, second player, okay? And it's finite, the game is finite. So there's an algorithm that will decide. You can show it has to be one or the other because the second player could mimic the first player with kind of a pairing strategy. And so you can show that it has to be one way or the other. But we don't know any algorithm anyway. We don't know there Are cases where you can prove the existence of a solution but nobody knows any way how to find it. More like the algorithm question. There's a very powerful theorem in graph theory by Robinson and Seymour that says that every class of graphs that is closed undertaking minors has a polynomial time algorithm to determine whether it's in this class or not. Now, a class of graphs, e.g. planar graphs. These are graphs that you can draw in a plane without crossing lines. And a planar graph is taking minors means that you can shrink an edge into. Into a point or you can delete an edge. And so you start with a planar graph and shrink any edge to a point is still planar. Delete an edge is still planar. Okay now but there are millions of different ways to describe a family of graphics that still is remains the same undertaking Minor and Robertson Seymour proved that any such family of graphs there's a finite number of minimum graphs that are obstructions. So that if, if it's not in the family then then it has to contain. Then there has to be a way to shrink it down. And until you get one of these bad minimum graphs that's not in the family. In the case of a planar graph, the minimum graph is a five pointed star with everything pointing to another. And the minimum graph consisting of trying to connect three utilities to three houses without crossing lines. And so there are two bad graphs that are not planar. And every non planar graph contains one of these two bad graphs by shrinking and removing edges.
Sorry, can you say it again? So he proved that there's a finite number of these bad guys.
There's always a found. So somebody says here's a family.
It's hard to believe.
And they PR it's sequence of 20 papers. I mean and it's deep work, but.
It, you know, it's because that's for any arbitrary class.
So it's for any arbitrary class that's closed under taking minors that's closed under.
Maybe I'm not understanding because it seems like a lot of them are closed under taking minors.
Almost all the important classes of graphs are. There are tons of such graphs, but.
Also.
Hundreds of them that arise in applications. I have a book over here called Classes of Graphs and it's amazing how many different classes of graphs that people have looked at.
So why do you bring up this theorem or this proof?
Now there are lots of algorithms that are known for special classes of graphs. For example, if I have a certain. If I have a chordal graph, then I can color it efficiently. If I have some kind of graphs. It'll make a great network, various things. So you'd like to test somebody gives you a graph. Oh, is it in this family of graphs? If so, then I can go to the library and find an algorithm that's going to solve my problem on that graph. Okay, so we want to have a graph that says algorithm, that says, you give me a graph, I'll tell you whether it's in this family or not. And so all I have to do is test whether or not does this given graph have a minor? That's one of the bad ones. A minor is everything you can get by shrinking and removing it. And given any minor, there's a polynomial time algorithm saying I can tell whether this is a minor of you and there's a finite number of bad cases. So I just try, you know, does it have this bad case polynomial time? I got the answer. Does it have this bad case polynomial time? I got the answer total polynomial time. And so I've solved the problem. However, all we know is that the number of minors is finite. We don't know what. We might only know one or two of those minors, but we don't know that if we've got 20 of them, we don't know there might be 21, 25. All we know is that it's finite. So here we have a polynomial time algorithm that we don't know.
That's a really great example of what you worry about or why you think P equals NP won't be useful. But still, why do you hold the intuition that P equals np?
Because you have to rule out so many possible algorithms as being not working. You can take the graph and you can represent it as in terms of certain prime numbers, and then you can multiply those together and then you can take the bitwise and, and construct some certain constant in polynomial time. And then that's, you know, perfectly valid algorithm. And there's so many algorithms of that kind. A lot of times we see random, you take data and, and we get coincidences that, that, that some fairly random looking number actually is useful because, because. It happens to solve a problem just because there's so many hairs on your head. But it seems like unlikely that two people are going to have the same number of hairs on their head. But they're obvious. But you can count how many people there are and how many hairs on their head. So there must be people walking around in the country that have the same number of hairs on their head. Well, that's a kind of a coincidence that you might say also, you know, this, this particular combination of operations just happens to prove that a graph is, has a Hamiltonian path. I see lots of cases where unexpected things happen when you have enough, enough possibilities.
So because the space of possibility is so huge, your intuition, you have to.
Rule them all out. And so that's the reason for my intuition. Is it by no means a proof. I mean, some people say, you know, well, P can't equal np because you've had all these smart people, you know, the smartest designers of algorithms have been racking their brains for years and years and, and there's million dollar prizes out there. And you know, none of them, nobody has thought of the algorithm. So it must, there must be no such algorithm. On the other hand, I can use exactly the same logic and I can say, well, P must be equal to NP because there's so many smart people out here been trying to prove it unequal to np, and they've all failed.
You know, this kind of reminds me of the discussion about the search for aliens. We've been trying to look for them and we haven't found them yet, therefore they don't exist. But you can show that there's so many planets out there that they very possibly could exist.
Yeah.
And right.
And then there's also the possibility that they exist, but they all discovered machine learning or something and then blew each other up.
