Video 2-1: P and NP Informally

0:02 In the next chapter, we'll look at classic complexity theory. Essentially, the thing that I in the last unit I criticized a bit for being maybe overly pessimistic or uh bit too much focused on the worst case and all these um pitfalls that we identified or loopholes that you can peek into this or put into this theory. Before we uh go further into each of these loopholes, let's see what is behind complexity theory.

0:34 Um let's start with the informal version that we've seen to some degree last time as well. My metaphor for this is that some problems tend to be hard nuts to crack. And uh maybe a coconut is is an example of such a hard nut. And here's um the equivalent of a hard nut in the world of algorithmic problems. Maybe the most famous of all, the traveling salesperson problem. Um formally, here this depends a bit how how people formalize this. Let's be very precise what the input is. Um so I'll always try to have the structure that if we're talking about some problem, there's a a given and a goal. Uh you could also say input and output, but I think goal is a bit nicer because it gives more freedom what that goal could look like. Uh so given is is essentially n cities. You could think of these just as being numbered from 1 to n.

1:31 Uh and then pairwise distances. So often times we think of these as points on the plane and it's a map of cities. Uh then each of these has a certain distance. But the graph is really complete, so I have a connection from anywhere to anywhere else. And in principle, any of these connections could have uh I'm sure I'm missing some.

2:03 >> Counting degrees. Um so, if first of all, all connections between any two cities are there and have some some value of how long it takes to get directly from city I to city J. That's the idea. There's no uh no connection that is forbidden. If you want to model that, you can put it at some uh ridiculously large distance value, then any good solution will not use that connection. Right? And the goal is to find the shortest route through these cities, where route means uh visiting every city exactly once. So, maybe uh bit too big. That's a bit too small. Maybe you >> [laughter] >> not a rectangle. Uh maybe you want to go like this and then close the tour in this way. There's many options. How many? Well, essentially as many as there are uh permutations of the cities divided by n because we don't care where we start. It's a closed loop.

3:05 Um but in principle, it's n minus one factorial different options. And that is a huge number even for relatively moderate n. This blows up very quickly. So, if you if your approach were to go through all the possible tours and determine the total length, which uh I guess we should also say the length of a tour is defined as the sum of the lengths of these individual parts.

3:53 I'll make this a bit more formal later when we return to the problem. For now, it's just a a metaphor for this rather hard nut to crack because, as you may know, is this is one of the problems that are known to be NP-complete. And so, we don't know a general efficient algorithm that solves this problem optimally in in the sense that it finds the exact shortest tour. And you already see this all these potential loopholes that you could try to explore.

4:26 Now, what does that mean to say this is a hard nut? It would be cool if we could somehow prove um that it's just not it's not just our inability to find some efficient algorithm that always works, etc. But rather um give some good reasons for that.

4:47 And we've already seen this uh cartoon last time. The goal is we would love to have a definitive proof that no such algorithm exists, but alas, we haven't found such a proof either. Neither have we found any algorithm, so we're in the unknown. But we can try to relate this problem to other problems. And because many people worked on many of these problems and all of them failed, maybe um we're excused for also failing. So, the essence of complexity theory is to compare the hardness of different nuts. And uh if you look for nuts that are even harder than a coconut, I think that's uh my best guess, it's a macadamia. They're not quite to scale. This this um It didn't work out right. Also, it looked too cute, but still these are really hard to crack. The shell is without a proper device essentially um impenetrable. So, maybe we can somehow relate one problem to another and say that our our problem that we try to estimate how hard it is to solve the traveling salesperson problem is um somehow in Well, this would be the new problem. Uh say this is the traveling salesperson problem.

5:59 Doesn't fit the picture from the previous slide. But maybe we can relate it to some other problem where we've already agreed upon that it's hard. And if this new problem is even harder, then we agree that there's little hope. Uh the formal notion for that is a polynomial time reduction or card reduction. We'll recap that later. The intuitive idea is um if this problem is already hard and this problem B is at least as hard as A, then B is a hard nut to And more formally, what does that mean for algorithms? Well, hard means likely probably not in a probabilistic sense. We uh in terms of uh the belief sense, we think there's probably no efficient algorithm for problem A. And efficient here means polynomial time. We'll also come back to that. Uh that's a convention more than a law of nature, but it's the one that makes the theory stable. And the second part, this this relation means any efficient algorithm for B, if it if there were one, would imply an efficient algorithm for A.

7:06 Now, those two things together mean that also probably there's no efficient algorithm for B. Otherwise, this reduction would immediately give one for A and that would contradict our belief here that probably there is no such algorithm. Okay. So far so good. I think at that level of abstraction easy and familiar. Um in terms of the complexity classes that you also will be familiar with the P and NP question. Um what this comes down to is we have a class P, the easy problems, where it's um possible to find where we know that we have an efficient algorithm. Formally, there's a polynomial so that in running time bounded by the polynomial of the input size, we can find a solution to this problem. Optimal and for worst case, yada yada yada. Uh then that problem is in class P.

8:14 And the other pro- protagonist here is the class NP, where we don't know whether such an algorithm exists. We only know that if you give me an instance of this problem and a candidate solution, then there is an efficient algorithm that checks whether that candidate solution is valid. Not whether it's optimal, whether it's the best, the shortest tour, but just whether it's a valid tour in the TSP problem at all. You already see this is rather easy for the TSP problem. All I need to do is check that you've listed all all of the N cities. Not so hard. Maybe compute the total length and check if it's uh below a threshold, but certainly this is much much easier than coming up with a tour.

8:58 As you may know, this name comes from something different. I would say this is a a historical nuisance, um because now it's easy to mistake NP to mean not polynomial, and that's of course very far from the truth. We don't know that. It stands for nondeterministic polynomial. We'll come back to that as well. Um and then the big question is whether these two classes are equal. And basically, people don't believe that. We think Well, it's it's clear that P is a subset of NP, but we think it's a proper subset, which means the two classes are dis- are different. And when I last gave this, I had to explain what the Millennium Problems are. I think now they're a bit more in common knowledge or more in the focus of media uh since some of these got solved. Whether or not by humans or by AIs is a different question. Um P versus NP is one of those problems, and I think people don't even have the idea of how to start to prove or disprove this.

10:01 So, I don't believe AI will help us in this anytime soon. But of course it would be very exciting if it did if it did. Even even if P and NP would be the same though, not all that much necessarily follows. A huge nice piece of theory goes goes to the bin, but it's not obvious whether it has practical implications. I want to stress that because if you Google for P and NP, you find all sorts of hyperbolic nonsense. Um one option could be somebody proves P is NP in a non-constructive way, or in a way that gives you algorithms where the polynomial has a degree of 10 to the 10 to the 10.

10:47 That will not make make any difference for any application. It could be without any consequences for the practical applications of of all these problems.

11:01 Nevertheless, it's a very beautiful theory and so far it stands. Let's have a look at this question from before again. Because the other thing um apart from being a bit critical of potential consequences of solving this problem one way or the other is you should be really careful what exactly the formal statement is because there again uh it's it's lovely to reason about P being problems where you can find a solution easily and NP where you can only verify it and then you can extend this to all sorts of problems. Maybe it's easier to find proofs than to verify them uh the other way around. Maybe it's easier to verify a proof that you're given than to find one. All these things are um somehow fun fun chats. But it's a bit hard to tie them to the theory. And so you should make you should be able to make the distinction. That's what this question ultimately gets to.

12:00 Um anyone still thinking? There's three votes in. There's a few more people here. No idea is a valid option. Um the problem is a bit of a a strange way to put this, but this is on purpose.

12:22 The reason for this question is to see whether you're familiar with this uh theory already. Not really uh my expectation that you're able to solve this from what I've told you so far. Okay? If you know how to answer this properly, then you know it because of some previous modules.

12:44 Okay. Uh let's see where we stand. Various opinions. Um So the fun thing is that this problem is defined in such a way that I can give you a polynomial time algorithm. Even though it's a stupid one that is not very practical. Um how would you check if a given graph has a clique of size 10? A clique of size 10 is a subgraph of 10 vertices where all possible connections exist.

13:29 we can find an algorithm uh the the the problem is given some graph. That's vertices and then it should be a rather dense graph otherwise it doesn't make much sense, but let me try not to draw this into much uh detail. So there's no assumption on the graph. A clique of size say four would be something like this where you have a subgraph I can find four vertices and among those all edges exist in the graph. This is for size four, that's a four clique.

14:08 A 10 clique is the same just a bit bigger and I'm reluctant to draw it. Now how can I check for such um the existence of such a 10 clique?

14:29 A stupid way would be 10 nested for loops. Where I go with some variable over all possible vertices. Now this is a nested for loop with a total run time of n to the 10th. Not particularly fast but it's a polynomial because 10 is a constant. And so inside here um check if And use some some graph theory notation that makes this a bit concise just to say that's the induced subgraph. I'm taking my graph G I only look at the vertices in my subset V of the this is of course not good.

15:27 Let's make it lazy but not wrong. So I take my 10 vertices and call that subset of vertices of 10 vertices V prime. Then I can take my induced subgraph on these 10 vertices and check if that's a K10, otherwise known as the complete graph on 10 vertices. Uh you could also spell out all the 10 the five times nine different edges explicitly. I'm I'm trying to be even here a bit stupid and ridiculous just to show you that this algorithm is very very simple. Very simple to write down. Of course the running time in the worst case is n to the 10th because that's as the number of sets roughly. Um that's not very fast but it is a polynomial. Which proves that this problem is in in P. It's of course also in NP because that's a subset. That's a non not so interesting question. But it won't be NP-complete for reasons that you'll see in a sec. Um and it's certainly not not in NP.

16:40 Okay, so I'm halfway happy that a few people got led astray on this on this question. So um that the signal comes comes across that you need to read carefully what polynomial time means. And whether or not that's a practically useful algorithm again is um is a very different question.