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? 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 because, 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 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?

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 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 hex 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. 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. In other words, 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 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, shrink any edge to a point, it's still planar.

Delete an edge, it's still planar. 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 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 where everything points 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 that again? So he proved that there's a finite number of these bad graphs. - There's always a finite number. So somebody says, "Here's a family of--" - It's hard to believe. - It's very surprising. - And they proved in this sequence of 20 papers, I mean, and it's deep work.

But it's-- - Because that's for any arbitrary class. So it's for any-- - 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 "Fact 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 classes 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, various things. So you'd like to test it. 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, "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, 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 construct some certain constant in polynomial time.

And then that's a perfectly valid algorithm. And there are 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 unlikely that two people are going to have the same number of hairs on their head. 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, 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 just says- - They have to rule them all out.

And so that's the reason for my intuition. It's by no means a proof. I mean, some people say, well, P can't equal NP because you've had all these smart people. The smartest designers of algorithms have been racking their brains for years and years. And there's million dollar prizes out there.

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 have 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. - 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.

- Right. - So I think there's a lot of research that can be done on the human side of things. - Yeah. - I mean, I think there's a lot of research that can be done on the human side of things. I mean, there's a lot of work that could be done on the human side of things.

I mean, there's a lot of research that could be done on the human side of things. - Right. - And I think there's a lot of work that could be done on the human side of things. - Yeah. - So I think there's a lot of work that could be done on the human side of things.

- Right. - And I think there's a lot of work that could be done on the human side of things. - Right. - So that's what I'm trying to say. - Yeah.