Video 2-4: The Classes P and NP

0:02 In the next section we'll look at how to define formally these classes P and NP that we started with and that this this this whole section is about in terms of our Turing machines. Um for that uh we need to define something that we haven't touched on yet. P and NP are classes of problems, not specific machines. Right? So, they're they're not a class of algorithms, they're class of algorithmic problems. And so, we need to go from individual runs on individual inputs to something um family of inputs that you can tie together. Uh so, the first step towards that is that we say uh Turing machine that may uh accept inputs of different length has a um a a function that says how long it might take depending on the input size. So, formally I have some uh um Turing machine A that implements a mapping. So, it's taken it's taking strings from some input alphabet. Yeah.

1:12 It takes uh strings from some input input alphabet and writes strings from some output alphabet at the end onto the tape. So, whenever you're given some some input from this alphabet of a certain length, then little time A for this machine on this input is the uh time it takes on this input just as we had the definition before.

1:38 Uh here I guess it's uh it's generalized to arbitrary algorithms, but then we need this in particular for Turing machines. That is the the little time. Lowercase time and space. The uppercase time and space generalizes that to all inputs of a certain length. So, it just the worst-case time over all inputs of a certain length. That's uh expressed by the maximum. So, same same setup, but now I have uh this function from N to N. And it's defined in terms of the little one little time. Uh where the important part here is is just this superscript. Uh so, formal language notation, right? Sigma is some some alphabet, so a finite set of symbols. And sigma to the power N means I take N exactly N symbols and make a string of length exactly N. So, capital time is the longest time it takes on any input of size N, same for space. That's the first step.

2:44 Now, we can talk about uh algorithmic problems. And for all of the complexity theory um at this point, we look at a special kind of problems, namely decision problems. So, these are problems that ask just a yes-no question. So, you can equivalently define them as a um a language or a set of words, namely all those words that have as answer yes. So, a decision problem is um is this lovely thing is a a language over some alphabet. And then it has some uh super set of this language, which is the allowable encodings. Uh you'll see in a second why this why this makes sense to have this intermediate thing. So, formally it just says that these are all strings and U is a super set of L. And an algorithm decides or solves this problem, decides this language if for any allowable encoding, so only the elements in U, the output of our machine, our algorithm is one exactly when this input is in L, and is zero for all the others.

3:53 Okay, so it computes the characteristic function of L but only on inputs from U. So, I allowed to exclude some inputs that are kind of don't even syntax check result.

4:11 Okay. Uh sometimes we can avoid this U and let me just write it more briefly. So, as an algorithmic problem, one level of abstraction higher, we ask problems of this type. Given some some word, is this in this fixed language L or not? That's the algorithmic question.

4:34 And um to tie this a bit back to some more more useful problems, if you think about our traveling sales person problem, this is not a yes-no question as we defined it before. I told you here are cities and the distances, what's the shortest route? I can turn that into a decision problem if I also give you a threshold. So, here are my cities and the distances, is there a tour? Is there a way to go round the cities with distance at most a total length at most capital D? And then it's a yes-no question. Uh we'll look at this later again a bit more systematically, but you can always go back to the other version um as long as these numbers are not completely crazy. Uh effectively, you can do a binary search for the right value. Right, you can ask uh can I do it with with 10 km? And if the answer is no, you make the distance bigger.

5:31 And once you get the answer, yes, it's possible, you can uh narrow down the range until you're precisely at the optimal solution. So, that way you can at least get the optimal length, the length of an optimal tour. And then yet another step is to also tease out the actual tour. But, all of this turns out to be a non-issue. The harder part is really the decision is there a tour of this of maximally this length at all or not? And to get all the way back to our formal decision problem, you also need to specify how do we encode an input to the traveling salesman problem as symbols, as a string for our Turing machine. And here, we'll again fudge it most of the time. There's some way, some sensible encoding. That's the usual tech phrase.

6:33 And what this means is that it shouldn't be stupidly wasteful. For example, it should not inflate your input with an exponential number of zeros at the end just to make the input look bigger. That would not be a sensible encoding. But, any somewhat sensible encoding is again a lot of leeway should be enough. So, the language would be all the encodings of input um instances for the traveling salesman problem including some threshold. Okay, you could maybe you could imagine you first write down n, the number of cities in binary. Then, you know there's going to be the matrix of distances coming. You know how many there are, so you write these numbers one after the other. It's almost a bit like uh um Kilonova problems or other competitive programming languages um systems where you you read in the input one after the other. Uh think of it a bit like that.

7:32 Okay. So, now we know how to find how to define algorithmic problems as decision problems. Uh for such an algorithmic problem, I can define upper and lower bounds by uh upper bound means there is an algorithm that has worst case running time the capital T bounded by this function. So, there is some way some algorithm that decides this algorithmic problem and doesn't take longer than a certain running time bound. Uh a lower bound statement for the complexity of this problem is the statement that every algorithm right? Harder to do. Every algorithm needs time at least that much in our model of computation. And then you can uh you can speak about optimal algorithms. I almost always want to give this in quotes because optimal is a is a bold statement and it means a very precise thing and not more. Namely uh exactly this. This up to these constant factors big O notation a matching upper and lower bound for the problem's complexity.

8:42 But it's always a statement about worst case and so on and so forth. But you you will see optimal used in this sense in the literature. So, in in that sense take it not as my favorite notation of how to express this but as the conventional way to do it.

9:08 Now we're getting close to um our goal. So far we've talked about the running time of a specific algorithm or specific Turing machine. Now we want to lift this to algorithmic problems. And um we do this. That's the I'm sorry for the third overload of time. Now the all caps time. Uh if you have good suggestions for how to make this less ambiguous, um I'm listening.

9:33 So, this is now a set of languages. Otherwise, you could say a set of algorithmic problems. Capital time is a set of problems for which there is a Turing machine that decides this language and has time bounded by this function F that I use as parameter here. And the side conditions of the Turing machine are deterministic and and total, always terminating. Okay, so this is the set of all algorithmic problems that I can solve with a given bound of the running time for the worst case. Okay?

10:14 Uh we need this always terminating, but this uh side remark. With that, we can define our class P, finally. An hour and something in. Uh the class P is the union of these of these classes of of this times uh for the classes of problems where the function is any polynomial. So, um you could informally also write something like this uh n to the big O of one or so. But um this is not a single function, it's a class of functions. So, I guess this is a bit more correct. But it's an infinite union. Any problem for which there is some polynomial so that there is a Turing machine that decides this problem with running time bounded by this polynomial is in P. And this is what people define as tractable problems or efficiently decidable problems. Where that's really just a definition overloading these English terms. It has this precise meaning and whether or not that's practically tractable is a different story.

11:28 That is P. One more missing, right? NP. Uh how can we define running time for non-deterministic machines? As with these awkward machines that may compute things in many different ways and one accepting run is enough. So, recall that something in the language means that there's just one uh, accepting computation potentially.

11:53 Uh, we always we assume also for the non-deterministic machines that they always terminate. So, even if they might branch out and they might uh, take longer and longer, there will be an eventual end to this. And so, um, this is just following from the definition we've had, the longest the supremum of all these defines the running time. It's worst case over the different computations at this level.

12:22 >> [snorts] >> And so, we can define um, an equivalent to this time set of problems, NTIME, the set of problems for which a non-deterministic machine computes decides this language and has time bounded by this function. So, at this point this is very analogous to the capital time. Only difference is that I'm allowing these non-deterministic machines here. And then NP is defined the same way as before as this union of all polynomials. Okay? Now, we finally know what these two classes are.