Video 2-4: P and NP formally

0:04 With that prep, we're uh now able to define formally what we had initially as as just a rough idea, these classes P and NP. So here again um essentially the same definition that we've seen on Turing machines uh on uh the more uh high level construction of of an algorithm. Uh here we have a different input and output alphabet. I don't remember if there's any case where we really need that. Uh there's a total mapping that this function uh that this algorithm computes. It takes a a string from this input alphabet and produces a string over the output alphabet. It's really the same like in the cheuring machine case, right? We had a a specific string that we start with go through the computation, reach a holding state, and then we've produced the output. Same thing. Um and then uh we denote by time uh small small case time of x the time and small case space is the the time complexity or space complexity that the algorithm has on this input. And this is not very rigorous, right? This is just saying there's something like time complexity.

1:14 uh but you can do uh you can do the formalization of over touring machines or you can get away with a more abstract cost measure for most cases. Nothing new and we could always go back to the the details. Uh the new bit is um we need a way to go from the time or space of an instance of a specific word or input X to something talking about the size of inputs which is where all the uh analysis of algorithms really gets started. Um so same setup and now the capital case time and space uh take not the input but a size as input and then it outputs the worst case running time. Okay. Uh the largest time it ever takes for a string of size n. So uh x is a string. So we can say how many letters it has. That's the input size. And space is totally analogous. Same thing. Okay, so that's just the notion that we treat all strings of the same length as one type of input and we take the the maximum over the time there. Um, so far we've mostly talked about functions that are computed. Now let's uh get back to algorithmic problems and I alluded to this in the beginning. We'll focus on decision problems which are uh formally a language. Um informally you're given an input and you're just asking a yes no question. And the yes instances are elements that are in the language. The no instances are elements not in the language. And an algorithm is supposed to uh to solve this problem by either outputting a one or outputting a zero. If x is in the language should output one otherwise zero. That's the characteristic function that we've seen Um I think this is all the same. The only new bit would be the notation. This calligraphic L of an algorithm again is is this uh this set L this language that's accepted by outputting a one. if you give it the element as input that's in the language. Uh so again decision problems you're given some some input and you're ask is this is it in the language that's a yes no question. If you find that hard to relate to typical algorithmic problems here's an example how it's used. Uh it could be the traveling salesperson problem. So the input there was this distance matrix and a threshold to turn it into a yes no question. You have to give it a bound on the tour length and then the question becomes is there a way to go through all the cities in this distance with this distance matrix so that the total length is at most d. Uh then the language would be some way to uh to specify that. So you would somehow have to encode the graph in a string and this number in a string combine the two things and that's your language because our Turing machines poor things they can only work with strings but I guess if the web has proven anything that uh everything's a string so it's not a restriction.

4:51 Okay, if we have um if we have an algorithmic problem, uh we could define an upper and a lower bound for the running time. In essentially the obvious way, we say an upper bound is uh a running time function is an upper bound for this problem. If there is an algorithm that solves this problem in that time and a lower bound for the problem is another function where we can somehow prove that every possible algorithm needs at least that much time. That's just coining these two terms because they're used in in algorithmic literature a lot. And uh people also use optimal although I'm I'm not a fan of this because it's so unspecific. Optimal just means an algorithm that is in the same theta class as some known lower bound. So you cannot improve the time of this algorithm for that problem by more than a constant factor.

5:51 Um that's what people in algorithm theory often mean when they say an optimal algorithm which is a a bit unfortunate because this optimal is only optimal if you ignore constant factors for large enough inputs and in the worst case.

6:18 Okay, we still haven't made it to P andnP, right? There's one step missing. Um we define classes of problems. Now uh that's the capital time all cap time given some running time function. So you bound now how much the problem is allowed to scale up in complexity given the input size. And then time of this function is the set of all languages or algorithmic problems for which we can find a Turing machine that u accepts this language and uses at most f of the input size as its running time. So here that's that's true for all. So again it's it's a kind of a worst case notion because it has to be true for all possible languages and all possible words in the language.

7:17 And based on that we can define the class P which is the union of all these time classes for all polomials. So all polomial functions is effectively you could have uh written this as the union over all constants C and then it's time of N to the C. uh it's a bit more convenient sometimes to write it like this but effectively there must be an upper bound on the running time of the form n to a constant n to a thousand is fine uh any constant c is fine but it has to be a constant not grow with n and any language in this class so any language for which we can find a touring machine that accepts it in time bounded by some polomial we call that attractable or efficiently decidable or efficiently computable class or language. That was P. So far so good. I know the pace today is a bit rough. Uh I want to cover as much ground so that you can you can do the mini seminar well. Um and at the same time for two for three quarters it should be repetition for you. I just don't know if you have done it with the same formalism at the same level of detail. So I thought uh the best compromise is to run through it quickly and show everything but not spend a ton of time and give you a fair chance of digesting it if you see it for the first time. But the video is there for you to rewatch and there's there's the books.

9:01 Um to define this other class NP, we need to come back to non-determinism. And this is just a recollection of what we've just covered. So maybe it's not so far away. A non-deterministic Turing machine accepts some language if there's some way of an computation that outputs one that's that rejects uh that accepts this this input. Uh but if a if a string is not in the language then every possible computation has to reject it. That's the flip side. So there's an asymmetry, right? It's it's easier to accept something in a way than to reject. If you reject, then you have to reject it in all possible computations. We restrict our attention to these always terminating Turing machines. Don't do infinite loops. Everything has to have uh an end. And yeah, we defined the time to be the longest possible computation if it's a nondeterministic machine. That's I've said that in detail before, but just to recap. Yep.

10:33 Well, nondeterminism um is still it still has a well- definfined length. Um it's not like parallelism that you can branch off and then come back at the end at some way. Right? Non-determinism just says there's many there's different options. Universe let me know which one to pick. I don't know. I have all of them are available and there's no there's no effective way to know which one to take. Maybe it'll become clear in a second when we have the the other formalism for this. Keep keep it in mind.

11:11 We have an a similar notion to time which is end time. That's same setup. We have a a running a bound for the running time. Now it's a set of all languages for which there is a non-deterministic during machine that accepts it in that time. Otherwise the same thing as time but n time means nondeterministic. Um and then the class NP is defined analogously to to P. Again the union of all polomials but then using end time. And that sounds like not such a big deal in the diff in the definition very similar right should be uh that the problems are also similar but of course you already know that that's not the case.