back to index

Donald Knuth: P=NP | AI Podcast Clips


Whisper Transcript | Transcript Only Page

00:00:00.000 | You've mentioned over the past few years that you believe P may be equal to NP, but that
00:00:07.000 | it's not really, you know, if somebody does prove that P equals NP, it will not directly
00:00:13.120 | lead to an actual algorithm to solve difficult problems.
00:00:18.300 | Can you explain your intuition here?
00:00:19.920 | Has it been changed?
00:00:21.880 | And in general, on the difference between easy and difficult problems of P and NP and
00:00:26.560 | so on?
00:00:27.560 | So the popular idea is if an algorithm exists, then somebody will find it.
00:00:37.040 | And it's just a matter of writing it down.
00:00:43.080 | But many more algorithms exist than anybody can understand or ever make use of.
00:00:50.400 | Or discover, yeah.
00:00:51.780 | Because they're just way beyond human comprehension.
00:00:55.160 | The total number of algorithms is more than mind-boggling.
00:01:02.840 | So we have situations now where we know that algorithms exist, but we don't know, we don't
00:01:08.600 | have the foggiest idea what the algorithms are.
00:01:11.960 | There are simple examples based on game playing where you have, where you say, well, there
00:01:20.800 | must be an algorithm that exists to win in the game of hex because, for the first player
00:01:26.840 | to win in the game of hex, because hex is always either a win for the first player or
00:01:32.480 | the second player.
00:01:33.480 | Well, what's the game of hex?
00:01:34.480 | There's a game of hex which is based on putting pebbles onto a hexagonal board, and the white
00:01:40.960 | player tries to get a white path from left to right, and the black player tries to get
00:01:45.560 | a black path from bottom to top.
00:01:48.000 | And how does capture occur?
00:01:49.520 | And there's no capture.
00:01:51.360 | You just put pebbles down one at a time.
00:01:54.520 | But there's no draws because after all the white and black are played, there's either
00:01:58.560 | going to be a white path across from east to west or a black path from bottom to top.
00:02:04.080 | So there's always, you know, it's a perfect information game and people take turns like
00:02:10.800 | tic-tac-toe.
00:02:11.800 | And the hex board can be different sizes, but there's no possibility of a draw, and
00:02:20.720 | players move one at a time.
00:02:22.880 | And so it's got to be either a first player win or a second player win.
00:02:26.840 | Mathematically, you follow out all the trees and either there's always a win for the first
00:02:32.520 | player, second player, okay.
00:02:34.520 | And it's finite.
00:02:35.600 | The game is finite.
00:02:37.280 | There's an algorithm that will decide.
00:02:39.920 | You can show it has to be one or the other because the second player could mimic the
00:02:44.160 | first player with kind of a pairing strategy.
00:02:48.360 | And so you can show that it has to be one way or the other.
00:02:54.840 | But we don't know any algorithm anyway.
00:02:57.080 | We don't know.
00:02:58.080 | In other words, there are cases where you can prove the existence of a solution, but
00:03:04.800 | nobody knows any way how to find it.
00:03:06.960 | More like the algorithm question, there's a very powerful theorem in graph theory by
00:03:13.720 | Robinson and Seymour that says that every class of graphs that is closed under taking
00:03:22.440 | minors has a polynomial time algorithm to determine whether it's in this class or not.
00:03:29.480 | Now, a class of graphs, for example, planar graphs, these are graphs that you can draw
00:03:33.120 | in a plane without crossing lines.
00:03:36.920 | And a planar graph, taking minors means that you can shrink an edge into a point or you
00:03:44.440 | can delete an edge.
00:03:47.560 | And so you start with a planar graph, shrink any edge to a point, it's still planar.
00:03:52.920 | Delete an edge, it's still planar.
00:03:56.960 | But there are millions of different ways to describe a family of graphs that still remains
00:04:09.840 | the same under taking minor.
00:04:12.480 | And Robertson and Seymour proved that any such family of graphs, there's a finite number
00:04:18.280 | of minimum graphs that are obstructions.
00:04:24.560 | So that if it's not in the family, then it has to contain-- then there has to be a way
00:04:33.000 | to shrink it down until you get one of these bad minimum graphs that's not in the family.
00:04:40.040 | In the case of a planar graph, the minimum graph is a five-pointed star where everything
00:04:45.360 | points to another, and the minimum graph consisting of trying to connect three utilities to three
00:04:50.560 | houses without crossing lines.
00:04:52.920 | And so there are two bad graphs that are not planar.
00:04:56.680 | And every non-planar graph contains one of these two bad graphs by shrinking and removing
00:05:04.960 | edges.
00:05:05.960 | - Sorry, can you say that again?
00:05:06.960 | So he proved that there's a finite number of these bad graphs.
00:05:10.160 | - There's always a finite number.
00:05:11.600 | So somebody says, "Here's a family of--"
00:05:13.480 | - It's hard to believe.
00:05:14.480 | - It's very surprising.
00:05:15.480 | - And they proved in this sequence of 20 papers, I mean, and it's deep work.
00:05:21.920 | But it's--
00:05:22.920 | - Because that's for any arbitrary class.
00:05:25.680 | So it's for any--
00:05:26.680 | - Any arbitrary class that's closed under taking minors.
00:05:29.240 | - That's closed under-- maybe I'm not understanding, because it seems like a lot of them are closed
00:05:33.880 | under taking minors.
00:05:35.320 | - Almost all the important classes of graphs are.
00:05:38.200 | There are tons of such graphs, but also hundreds of them that arise in applications.
00:05:45.600 | I have a book over here called "Fact Classes of Graphs," and it's amazing how many different
00:05:55.360 | classes of graphs that people have looked at.
00:05:56.960 | - So why do you bring up this theorem, or this proof?
00:06:00.880 | - So now, there's lots of algorithms that are known for special classes of graphs.
00:06:05.720 | For example, if I have a chordal graph, then I can color it efficiently.
00:06:12.000 | If I have some kind of graphs, it'll make a great network, various things.
00:06:17.080 | So you'd like to test it.
00:06:18.880 | Somebody gives you a graph, and says, "Oh, is it in this family of graphs?"
00:06:22.960 | If so, then I can go to the library and find an algorithm that's going to solve my problem
00:06:29.120 | on that graph.
00:06:31.120 | - Okay, so we want to have a graph that says, an algorithm that says, "Give me a graph,
00:06:41.520 | I'll tell you whether it's in this family or not."
00:06:47.200 | And so all I have to do is test whether or not, does this given graph have a minor that's
00:06:53.840 | one of the bad ones?
00:06:55.280 | A minor is everything you can get by shrinking and removing it.
00:07:00.120 | And given any minor, there's a polynomial time algorithm saying, "I can tell whether
00:07:04.400 | this is a minor of you."
00:07:08.000 | And there's a finite number of bad cases.
00:07:10.000 | So I just try, does it have this bad case?
00:07:13.840 | Polynomial time, I got the answer.
00:07:14.840 | Does it have this bad case?
00:07:16.840 | Polynomial time, I got the answer.
00:07:19.720 | Total polynomial time.
00:07:21.720 | And so I've solved the problem.
00:07:23.520 | However, all we know is that the number of minors is finite.
00:07:26.960 | We don't know what, we might only know one or two of those minors, but we don't know
00:07:31.360 | that if we've got 20 of them, we don't know there might be 21, 25.
00:07:37.640 | All we know is that it's finite.
00:07:41.040 | So here we have a polynomial time algorithm that we don't know.
00:07:44.880 | - That's a really great example of what you worry about or why you think P equals NP won't
00:07:50.040 | be useful.
00:07:51.760 | But still, why do you hold the intuition that P equals NP?
00:07:58.480 | - Because you have to rule out so many possible algorithms as being not working.
00:08:10.360 | You can take the graph and you can represent it as in terms of certain prime numbers, and
00:08:16.640 | then you can multiply those together, and then you can take the bitwise and construct
00:08:26.240 | some certain constant in polynomial time.
00:08:28.320 | And then that's a perfectly valid algorithm.
00:08:31.760 | And there are so many algorithms of that kind.
00:08:34.760 | A lot of times we see random, you take data and we get coincidences that some fairly random
00:08:48.040 | looking number actually is useful because it happens to solve a problem just because
00:08:58.360 | there's so many hairs on your head.
00:09:05.000 | But it seems unlikely that two people are going to have the same number of hairs on
00:09:10.440 | their head.
00:09:13.480 | But you can count how many people there are and how many hairs on their head.
00:09:18.680 | So there must be people walking around in the country that have the same number of hairs
00:09:21.960 | on their head.
00:09:22.960 | Well, that's a kind of a coincidence that you might say also, this particular combination
00:09:28.560 | of operations just happens to prove that a graph has a Hamiltonian path.
00:09:35.080 | I see lots of cases where unexpected things happen when you have enough possibilities.
00:09:42.560 | - So because the space of possibility is so huge, your intuition just says-
00:09:46.080 | - They have to rule them all out.
00:09:47.720 | And so that's the reason for my intuition.
00:09:50.160 | It's by no means a proof.
00:09:51.520 | I mean, some people say, well, P can't equal NP because you've had all these smart people.
00:10:01.200 | The smartest designers of algorithms have been racking their brains for years and years.
00:10:07.640 | And there's million dollar prizes out there.
00:10:11.280 | Nobody has thought of the algorithm.
00:10:14.520 | So there must be no such algorithm.
00:10:17.560 | On the other hand, I can use exactly the same logic and I can say, well, P must be equal
00:10:23.640 | to NP because there's so many smart people out here have been trying to prove it unequal
00:10:27.320 | to NP and they've all failed.
00:10:32.760 | - This kind of reminds me of the discussion about the search for aliens.
00:10:36.760 | We've been trying to look for them and we haven't found them yet, therefore they don't
00:10:40.600 | exist.
00:10:41.600 | But you can show that there's so many planets out there that they very possibly could exist.
00:10:47.320 | - Right.
00:10:48.320 | And then there's also the possibility that they exist, but they all discovered machine
00:10:54.960 | learning or something and then blew each other up.
00:10:59.120 | - Right.
00:11:00.120 | - So I think there's a lot of research that can be done on the human side of things.
00:11:01.120 | - Yeah.
00:11:02.120 | - I mean, I think there's a lot of research that can be done on the human side of things.
00:11:03.120 | I mean, there's a lot of work that could be done on the human side of things.
00:11:04.120 | I mean, there's a lot of research that could be done on the human side of things.
00:11:05.120 | - Right.
00:11:06.120 | - And I think there's a lot of work that could be done on the human side of things.
00:11:07.120 | - Yeah.
00:11:08.120 | - So I think there's a lot of work that could be done on the human side of things.
00:11:09.120 | - Right.
00:11:10.120 | - And I think there's a lot of work that could be done on the human side of things.
00:11:11.120 | - Right.
00:11:12.120 | - So that's what I'm trying to say.
00:11:13.120 | - Yeah.
00:11:14.120 | [BLANK_AUDIO]