Full episode with Donald Knuth (Dec 2019): https://www.youtube.com/watch?v=2BdBfsXbST8
Clips channel (Lex Clips): https://www.youtube.com/lexclips
Main channel (Lex Fridman): https://www.youtube.com/lexfridman
(more links below)

Podcast full episodes playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4

Podcasts clips playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOeciFP3CBCIEElOJeitOr41

Podcast website:
https://lexfridman.com/ai

Podcast on Apple Podcasts (iTunes):
https://apple.co/2lwqZIr

Podcast on Spotify:
https://spoti.fi/2nEwCF8

Podcast RSS:
https://lexfridman.com/category/ai/feed/

Donald Knuth is one of the greatest and most impactful computer scientists and mathematicians ever. He is the recipient in 1974 of the Turing Award, considered the Nobel Prize of computing. He is the author of the multi-volume work, the magnum opus, The Art of Computer Programming. He made several key contributions to the rigorous analysis of the computational complexity of algorithms. He popularized asymptotic notation, that we all affectionately know as the big-O notation. He also created the TeX typesetting which most computer scientists, physicists, mathematicians, and scientists and engineers use to write technical papers and make them look beautiful.

Subscribe to this YouTube channel or connect on:
- Twitter: https://twitter.com/lexfridman
- LinkedIn: https://www.linkedin.com/in/lexfridman
- Facebook: https://www.facebook.com/lexfridman
- Instagram: https://www.instagram.com/lexfridman
- Medium: https://medium.com/@lexfridman
- Support on Patreon: https://www.patreon.com/lexfridman

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.

And in general, on the difference between easy and difficult problems of P and 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.

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 algorithm exists, 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

There's a game of hex which is 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.

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 east to west, or a black path from bottom to top.

So there's always, you know, it's a perfect information game and people take turns like tic-tac-toe.

And the heck board can be different sizes, but there's no possibility of a draw.

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 there's always a win for the first player, second player, OK.

So there's an algorithm that will decide.

You can show it has to be 1 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 1 way or the other.

In other words, there are cases where you can prove the existence of a solution, but nobody knows any way how to find it.

But 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 under taking minors has a polynomial time algorithm to determine whether it's in this class or not.

Now, a class of graphs, for example, planar graphs.

These are graphs that you can draw in a plane without crossing lines.

And a planar graph, taking minors means that you can shrink an edge into a point, or you can delete an edge.

And so you start with a planar graph and shrink any edge to a point, it's still planar.

Now, but there are millions of different ways to describe a family of graphs that still remains the same under taking minor.

And Robertson and Seymour proved that any such family of graphs, there's a finite number of minimum graphs that are obstructions.

So that if it's not in the family, then it has to contain, then there has to be a way to shrink it down until you get 1 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 where everything points to another.

And the minimum graph consisting of trying to connect 3 utilities to 3 houses without crossing lines.

And so there are 2 bad graphs that are not planar.

And every non-planar graph contains 1 of these 2 bad graphs by shrinking and removing edges.

So he proved that there's a finite number of these bad graphs.

And they proved in this sequence of 20 papers, I mean, it's deep work, but it's a-

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 ticking 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?

So now there's lots of algorithms that are known for special kinds of graphs.

For example, 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.

Somebody gives you a graph, and says, 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.

So we want to have a graph that says, an 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?

A minor is everything you can get by shrinking and removing edges.

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?

However, all we know is that the number of minors is finite.

We don't know what that, we might only know 1 or 2 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, there's just some, 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 know, 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 a perfectly valid algorithm.

And there's so many algorithms of that kind.

A lot of times we see random, you take data and we get coincidences that some fairly random looking number actually is useful because it happens to solve a problem just because There's so many hairs on your head, but it seems like unlikely that 2 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.

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 particular combination of operations just happens to prove that a graph has a Hamiltonian path.

I see lots of cases where unexpected things happen when you have enough possibilities.

So because the space of possibility is so huge, your intuition

Some people say, well, P can't equal NP because you've had all these smart people.

The smartest designers of algorithms have been wracking their brains for years and years.

And there's million-dollar prizes out there.

And none of them, nobody has thought of the 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.

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.

And then there's also the possibility that they exist but they all discovered machine learning or something and then blew each other up.


Speaker 0: 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 and NP and so on?

Speaker 1: 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.

Speaker 0: Or discover, yeah.

Speaker 1: 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 algorithm exists, 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

Speaker 0: the second player. What's the game of hex?

Speaker 1: There's a game of hex which is 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.

Speaker 0: And how does capture occur?

Speaker 1: And there's no capture. You just put pebbles down 1 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 east to west, or a black path from bottom to top. So there's always, you know, it's a perfect information game and people take turns like tic-tac-toe. And the heck board can be different sizes, but there's no possibility of a draw.

And players move 1 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 there's always a win for the first player, second player, OK. And it's finite. The game is finite.

So there's an algorithm that will decide. You can show it has to be 1 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 1 way or the other. But we don't know any algorithm anyway.

We don't know. In other words, there are cases where you can prove the existence of a solution, but nobody knows any way how to find it. But 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 under taking minors has a polynomial time algorithm to determine whether it's in this class or not. Now, a class of graphs, for example, planar graphs. These are graphs that you can draw in a plane without crossing lines.

And a planar graph, taking minors means that you can shrink an edge into a point, or you can delete an edge. And so you start with a planar graph and shrink any edge to a point, it's still planar. Delete an edge, it's still planar. Okay. Now, but there are millions of different ways to describe a family of graphs that still remains the same under taking minor.

And Robertson and Seymour proved that any such family of graphs, there's a finite number of minimum graphs that are obstructions. So that if it's not in the family, then it has to contain, then there has to be a way to shrink it down until you get 1 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 where everything points to another. And the minimum graph consisting of trying to connect 3 utilities to 3 houses without crossing lines. And so there are 2 bad graphs that are not planar.

And every non-planar graph contains 1 of these 2 bad graphs by shrinking and removing edges.

Speaker 0: Sorry, can you say that again? So he proved that there's a finite number of these bad graphs.

Speaker 1: There's always a finite number. So somebody says here's a family of-

Speaker 0: It's hard to believe.

Speaker 1: And they proved in this sequence of 20 papers, I mean, it's deep work, but it's a-

Speaker 0: Because that's for any arbitrary class. So it's for any class.

Speaker 1: Any arbitrary class that's closed under taking minors.

Speaker 0: That's closed under, maybe I'm not understanding, because it seems like a lot of them are closed under ticking minors.

Speaker 1: 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.

Speaker 0: So why do you bring up this theorem, or this proof?

Speaker 1: So now there's lots of algorithms that are known for special kinds of graphs. For example, 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. So you'd like to test. Somebody gives you a graph, and says, 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, an algorithm that says, you give me a graph, I'll tell you whether it's in this family or not. Okay? And so all I have to do is test whether or not, does this given graph have a minor?

That's 1 of the bad ones. A minor is everything you can get by shrinking and removing edges. 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 that, we might only know 1 or 2 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, there's just some, all we know is that it's finite. So here we have a polynomial time algorithm that we don't know.

Speaker 0: 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?

Speaker 1: Because you have to rule out so many possible algorithms as being not working. You know, 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 a perfectly valid algorithm. And there's so many algorithms of that kind. A lot of times we see random, you take data and we get coincidences that some fairly random looking number actually is useful because it happens to solve a problem just because There's so many hairs on your head, but it seems like unlikely that 2 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.

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 particular combination of operations just happens to prove that a graph has a Hamiltonian path. I see lots of cases where unexpected things happen when you have enough possibilities.

Speaker 0: So because the space of possibility is so huge, your intuition

Speaker 1: just says it's up. They have to rule them all out. That's the reason for my intuition. It's by no means approved. Some people say, well, P can't equal NP because you've had all these smart people.

The smartest designers of algorithms have been wracking their brains for years and years. And there's million-dollar prizes out there. And none of them, nobody has thought of the algorithm. So, 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.

Speaker 0: 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. Yeah. But you can show that there's so many planets out there that they very possibly could exist. Yeah.

Right.

Speaker 1: And then there's also the possibility that they exist but they all discovered machine learning or something and then blew each other up. You you

See all Lex Fridman transcripts on Youtube

Donald Knuth: P=NP | AI Podcast Clips