Video 2-1: P and NP intuitively

0:04 Let's start with uh unit two uh a recap of classic complexity theory NP completeness and let's jump right in. So um we'll probably just get into some of the definitions for today. Um, I'll give you a bit of a motivation first that really should be easygoing and then we'll we'll try to be very careful in defining what what a computation is and what the models of computation are that we look at and then we can define these classes P and NP. Uh there's an alternative characterization that I want to touch on and then we get into the actual business of uh NP hardness and reductions.

0:52 As an all the module, we'll start with some computational problem which uh is always of this form that you're given some input and you're asked to produce a certain output. And it turns out that some of these questions just seem to be hard nuts. They seem not easy to solve, at least not quickly or uh in the all the usual sense. So um always exact and correct and uh efficient in a specific specific definition. And here's this example that I brought up before, but let's define it properly. Uh the traveling salesperson problem has as input uh a list of cities. These are just some identifiers. The real input are all the pair-wise distances. So just a big matrix of the distances between any pair of cities. uh it's it's n times n minus one because it's really without the diagonal right the the diagonal is just zero the distance is there uh so it's the distance matrix between those uh cities we don't make in the general case any assumptions about these distances that is important it does not need to be symmetric necessarily um it doesn't need to be a metric so it doesn't need to reflect uh the usual assumptions on on distances. It could in in general be arbitrary numbers in these entries of the matrix. Uh and then the question is can you find the shortest route trip a shortest round trip? um formally that's it's a permutation of the cities and then uh so I'm just going to write this as SI1 SI2 and so on up to SI. So the S1 up to I1 up to I N these are the integers one up to N.

2:58 I'll write this this shorthand for the first n integers. So that's a round trip. That's a weird round trip. I'm just listing the cities, but you you're supposed to imagine you go through the cities in that order and then you return back to the first one. And so the the cost of such a permutation would be summing up the distances that you travel. So you go from city I J to city I that's the first mistake I J + one say. Now I arrived at city SN. So I have to go back. So that's the last uh sumant that was missing. Now I've closed the circle. Okay. So to formally specify the problem, you would have to write it a bit more like this. On this first introduction slide, I didn't do it. Uh later on I I will. Um but um that's that's the way to make it make it clear. Now it seems we don't know how to find the best possible round trip in any uh meaningful way in this general case.

4:27 No such algorithm is known where efficient means polomial running time in the input size. Again we'll come we'll come to define this formally. So seems there is no efficient algorithm for this but that might just be us being incompetent. Can we prove that there is no such algorithm? As you may know uh no there is no proof that there is no such algorithm. The only thing we can do is give strong evidence that supports this as this this hypothesis. Uh but we don't have a proof. If that sounds like uh not a very strong day for theoretical computer science because it can't answer that question, we can do something. And uh that's this picture again as you've seen before, right? We can at least point to the fact that we can prove that it's as hard as some other problem that nobody solved. And how do you do this in complexity theory? I'm staying in this uh I'm getting hungry now, but I'm staying with nuts. So, that's a that's a macadamia. They're not to scale, right?

5:46 Uh but if you put them next to the same size, you couldn't see anything of the macadamia. But there have you ever tried to crack a macadmia with the shell? They're incredibly hard. Like there's no way with a normal nutcracker, no chance, right? you need a special screw in thingy and then even even then you often end up with the whole nut squished together with the well that's me at least. So uh this is standing for an even harder nut than the cocoon nut. Okay. Uh the idea in complexity theory is to compare problems with respect to the hardness of uh how complex they are to solve. And so we start with an old problem where the conventional wisdom is that it's it's not easy to solve and we try to find a new problem or we we have a new problem that where we don't know whether it's hard but we try to find some comparison. Uh we'll denote it by this lesser equal p for polomial time reduction. Again we'll come to it. Uh the intuitive idea is if if A is known as a hard to be a hard nut and B is at least as hard as A then well B is also a hard nut. Okay. And in complexity theory speak we would say A is NP hard which means that probably there is no efficient algorithm for problem A. Then we would show this this property which means that B reduces to A. And you can read this lesser equal as hardness. So B is harder than A in this specific sense which means um that's basically the definition of this lesser equal. If there's an efficient algorithm for B then there is an efficient algorithm for A. It's this implication. U for the experts that's a slight lie because we're usually doing carb reductions not Turing reductions.

7:45 Yeah, come back to that. But if we take these two things together like in the picture on the left, uh we get that B is NP hard and that again means probably no efficient algorithm for B. That's the picture you should always keep in mind and in particular you should use uh you should use the picture to memor to memorize what the lesser equal points in which in which direction it points and you reduce cracking one problem to cracking the other problem. You reduce B to Okay. What does uh what do these letters P and NP stand for?

8:50 um P is the class of problems for which there is a known algorithm that has polomial time which will equate with efficient. So what does that mean? A bit more specifically there's an algorithm that solves every instance every uh example of this problem P in a run in a time that is polomial in the encoding of this instance.

9:19 Okay. And here P stands for polomial because that's the running time of this algorithm. And it's the same as uh asking for an algorithm to find the solution. And NP is the class uh where the name is not as intuitive. It's the class of problems for which we can uh in polomial time verify if we're given a candidate solution for an instance. Then in polomial time we can check whether it's a correct in a correct solution for this instance. So we don't we don't check that it's an optimal solution say in the tsp problem. We would be given uh the distance matrix and a specific permutation of the cities. We still have no way of of knowing whether that is the best possible round trip. But if you give me uh the cities and the roundtrip and ask is that round trip shorter than some threshold I can answer that and that's what uh what this is really asking only for it's a very weak requirement. So NP stands for uh historically non-deterministically polomial. Uh again we'll come to that uh intuitively it's where a non-deterministic algorithm can find the solution.

10:38 um we'll show that these two things the definition here and this uh non-deterministic computation come down to the same thing even if they at first look different and so what's this question then um it's obvious that P is a subset of NP um it's most easy to see maybe for the boxes if you can solve a problem from from nothing then you can also check If a given solution is easy, you can you can just forget the solution and basically compute your own. Uh so that that's an that's an easy thing to observe and we think that the inclusion is strict which means that the two classes are not the same but again nobody knows. This is arguably the most important open problem of all of computer science depending on who you ask I guess. Um some people even include mathematics because many questions in math are um maybe more um more narrow but okay this is uh let's stay within theoretical computer science I guess there is no no discussion to be had and that's why uh why these classes are are so famous it's the qu the difference between solving a problem and checking a given solution which intuitively feel really very