Video 2-5: Nondeterminism = Verification

0:03 In the next section, we'll look at a different way to define NP which is equivalent. It's a different characterization, but which is a lot more intuitive to work with. Uh during the break, we had a quick discussion about non-determinism and how it is similar and maybe not similar to parallel algorithms. The main point I think is is worth uh mentioning for everyone. a non-deterministic machine can essentially spawn an exponential number of threats and not pay anything for it. And that's unrealistic. So just to reiterate, you cannot build a nondeterministic machine that simulates these problems in in NP in in any sensible way, in any efficient way. The point of this definition is is a different is a different one. uh it's sketching out what would be possible with these machines, but they're unrealistic. A different way to look at those is um via verifiers um also called sometimes certificates. And so the idea is is as follows. Uh we can we can define a different notion of accepting a language. It's a bit awkward at first, but you'll see it maps very naturally to typical problems like the traveling salesperson problem. Uh we have a language again and now an algorithm is given a word of the language but also some other thing namely a certificate which here will just have some binary string. So the input to the algorithm is a is a pair a word from a potential word from the language where we have to decide is it part of the language yes or no and some mysterious binary string. Now such an algorithm is a verifier for this language if the following holds for every uh um the language is exactly the set of all strings so that there is some binary string C a certificate so that the algorithm outputs one if given W and C. Okay.

2:08 And then u we say that this this binary string C is a proof for the fact that W is in the language. And that's precisely um I think that the term is is is intuitive and telling there um let's do an example first. So if if L is the traveling salesperson problem, so a yes instance is a distance matrix and a threshold so that the shortest tour with those distances actually has a th length less than the threshold. Okay, that would be the language L. What could be a certificate? Well, the roundtrip itself. So somehow encoded in binary. But if you if you give me an instance of the traveling saleserson problem, the graph encoded or the the distance is encoded and the threshold and you also present me a tour, I can check if that tour has total length less than the threshold. And if I find such a um such a such a proof such a s certificate, I can easily verify in polomial time as well uh that such an instance is part of the language tsp. On the other hand, if you give me an instance where the shortest round trip is longer, I might have a very hard time to find any proof because there is none. And this is where the definition says nothing about it. Okay. Uh I was jumping ahead of myself with this polomial time verifier.

3:41 Um this is just saying an algorithm is a verifier if it somehow solves this uh definition. So it accepts um a word with a with a proof if that um indeed is in the language and a verifier has is an algorithm. So it has some running time if that time to accept a word is polomial. Now just in the length of the word the certificate is excluded. Uh which also means that the certificate had better not be too long otherwise no algorithm has the time to even read it. So that naturally bounds without without explicitly mentioning it. The certificate cannot be substantially longer than than the input string otherwise it wouldn't be a useful one. proofs need to be readable. Um then we can define the class of problems BP those that can be efficiently verified by well all the languages for which there is a polomial time verifier A that accepts exactly this this language.

4:56 Okay. And again um the example was L could be TSP yes instances which was the uh the distance matrix and the threshold. I think that was the notation I used on slide initially. Uh but you know what I mean that's the distance matrix. You just write down all the numbers. You give it a threshold all the numbers and the yes instance means there is a round trip that has at most distance capital D. Uh let's spend a minute comparing these two things. Um after the proof I think it will not be surprising but maybe at first sight it is. These two classes are the same. NP and BP describe the same problems which means we can either think about non-determinism or we can think about verifiers. It's the same thing. This is a statement about a set equality. So we prove it by uh both inclusions.

6:11 And the first one is we show that NP oh come on is a subset of VP which means I'm going to pick some arbitrary language L in NP and we'll eventually want to show that this language is also in VP if it's in LP that means there is uh a non-deterministic Turing machine A let's call it M like before so that L is the language that's accepted by this nondeterministic Turing machine and um it's also polomial time I'll just write briefly poly time to mean That's what would be properly right the time it takes machine M on an input of size N is big O of some C and there exists a constant C such that that is true. Okay.

7:29 Now with this machine M, we're going to construct a verifier language. And so that one's supposed to get an input from the alphabet. Let's say uh L is a subset of some sigma star.

7:55 And this verifier is supposed to take some word of sigma star and some binary string. So let's take this uh sigma star and 01 star.

8:39 The core idea of the simulation is M is a nondeterministic machine. So we only know if X is in the language that there's some accepting computation in M. But it has these non-deterministic steps where we don't know which step to take in each possible case. So at each point in time, M has only a constant number of possible things to do because all its control is finite. Uh if you go back the the delta of some state and the current tape symbol, I don't know, let's call it a, it has that many different options.

9:27 and that's less than some some constant C. So we will use some log C rounded up. I'm just saying we use the binary bits in C to pick one of the possible outcomes that we one of the possible next steps in the nondeterministic computation. So in a way we use C as if some some uh uh all- knowing person had written down exactly which are the right steps to take so that they lead us to the accepting computation. Now in general we don't know which the accepting computation is but the good thing is the verifier also doesn't need to know. It gets the string C as an input and it's supposed to accept if there's some certificate. It doesn't need to know which one it is or find it.

10:38 Okay. And that's that's basically all we do. input then uh that's happening if and only if there is a some accepting computation. You could even formally write down what that computation looks like, right? It starts from a starting state and then it goes with a number of steps to some holding state and one.

11:19 But we don't need that here. uh so that uh it accepts the input x and that means there was a selection of possible next steps at each nondeterministic uh time Okay, so we we simulate the nondeterminism writing down the choices and uh if M accepts the string s if and only if there exists a c so that a accepts xc that means the language accepted by The verifier A is our language L and that means L is part of VP and that's the end of this first bit. It shows every language in NP is also in VP. So that's the inclusion part one. Now let's do the other direction. Uh we also want to show that VP is a subset of NP. Uh but the idea is very similar.

12:54 So we have an arbitrary language. So we start with a verifier or L arbitrary language in VP and um we construct the nondeterministic Turing There's also poly time I can do this properly.

13:34 Uh so there's a non there's a poly time verifier for a we construct a nondeterministic poly time throwing machine for uh for this language where um we use the nondeterminism to guess the certificate.

14:06 nondeterministically. What that means is it's a binary string. So I'm going to do a number of steps where in each point I can do one of two outcomes and one writes a zero, one writes a one into my uh string C. And I'm I'm doing this non-deterministically which means someone has to figure out the right path. I'm not going to do it. I'm nondeterministic. Uh but that way I can effectively try all possible strings C. But it's nondeterministic. So I'm not even paying for it. And then for the rest I'm just simulating a and this part will be deterministic. I don't need to do any further guessing steps there. and you can work out the same the running time stays the same. Um you don't know how long the string C in general has to be but we can bound it by how much time A has. So you you don't have to generate an arbitrarily long string or you could even interleaf the things and be smart.

15:09 So you only um you only generate the next bit of the string C when A in its computation accesses it before you read the that bit. It is unrelevant. So you could also delay the guess it on demand basically. Uh but the same same thing as above here is true. Uh if there's a way to make the verifier accept if there is a proof then there is a way that the nondeterministic machine uses the right steps to guess that string and then it simulates it. So it accepts the same strings. So that language is in NP. And that concludes the proof because then every language in VP is also in NP. We already know every language in NP is already in BP. So the two are the same. Okay.

16:13 uh this is useful whenever you want to show that some problem is in NP because again um if you if you were to uh apply this to say the traveling salesperson problem you can show that it's in NP by showing it is in VP as I sketched before if you give me a if you give me a distance matrix and a threshold and a round trip it's really easy to just sum up the cost of the round trip and check if it's smaller than D. That doesn't even that's just linear time or