Video 2-6: VP = NP

0:02 Um, I've promised that these two things are the same. This class NP we defined last time based on nondeterministic Turing machines and the class VP. And so I think it's insightful to give a a short proof even though it's not very hard. Um, let's just prove the two inclusions. So the first step, let's prove that NP is a subset of VP.

0:27 So we're given a language in NP. What does that mean? Well, by definition, there exists some Turing machine M. And the language that this Turing machine accepts is precisely our language L. And M is a polytime Turing machine.

0:57 And let me here introduce this this term a bit more. Poly time is my my shorthand for polomial running time or polomial time. But there's another thing attached to that. I think uh we we also use poly time to mean that there's a sensible encoding behind it. Now for the languages there's nothing to encode. If we speak about algorithmic problems, we always have to represent them as a formal language. Encode them as a string. And if you do that in a stupid way, then polomial time loses its meaning. The example I gave last time was suppose I give you a tiny instance of the traveling salesperson problem, but then append a gazillion zeros at the end just because I think that's a good idea. Then the input size of that problem is really large even though the actual instance isn't. And then running time is always defined with respect to the length of the input. But now my input is huge. So I get to spend a lot of time in the uh in the uh actual input size because the I've artificially blown up the this the virtual input size or so. So poly time also hides this fact that we assume a sensible encoding.

2:12 uh but really what it what it means for the touring machine is just there's some constancy uh so that um I'm practicing these definitions again a bit the time of this machine worst case overall inputs of length n is bounded by n to the c that's what polomial means after all right that's precisely that it's some it's bounded by some power of n. So that's that's just a very concise way of saying all that. Okay. So we have to show that there is a verifier. So we'll construct one.

3:13 And um I think here let's add this uh alphabet. Let's say this language is uh from some alphabet sigma star some subset thereof. So given a ver for verifier we're given an element like this where the first is an entry that could be uh a word from the language and the second part is some 01 string. Uh maybe worth stating once this star means an arbitrary number of characters including zero for that matter. So it could be the empty string. will usually not deal much with that any any problem you can add a few finite cases and it doesn't change the complexity. So the point about this um Turing machine here that I really should stress because it's NP is that this during machine is nondeterministic and so uh it occasionally in its computation is allowed to choose a path to continue and we would somehow magically have to know which one to take to check if it accepts And that our verifier cannot do. But our verifier can essentially use its certificate whenever the Turing machine decides one way or another um to decide which path to follow.

4:49 So in principle we simulate this machine M and there may be sequences of steps where it's uniquely decided what this successive step is. And um so this may or may not work right uh for a given uh certificate it might lead us to a non-accepting path for this machine M or it might lead us to an accepting path. We don't know up front but what we do know is if the machine has some accepting path there will be some certificate that leads us there. Uh another thing to stress I said here bits in plural because the non-determinism can be branching out in more than two ways. There could be a a whole number of possible successor steps or successor states. So uh in in the case we have I don't know for C choices you can simply do some binary encoding of this give each choice a number in binary and then use the bits to decide to take a whole block of bits to decide which which of those capital C steps to take.

6:40 So then what we observe is that if this machine M accepts X as an input that's the same as saying there is some computation for this machine when I started with X. So again, normally speaking, there's some starting state that we start with with X and then we do an arbitrary number of steps and we get to some alting state and there's the one written afterwards. Right? This is what computation meant. Uh we don't need to unfold that really here.

7:41 And this is the second step is by virtue of this construction. And here I'm not 100% rigorous because I didn't give you the full details of how this simulation should work. That would branch more into uh the question about universal Turing machines that we don't really need to get into. Um I think at this level of abstraction, let's let's leave it with there is a a string C to follow this computation. And so it would also accept our our input X and C. And in each of these cases is an if and only if. If there's any way to accept X, then I can simulate that. And if uh there's any way to make our verifier accept, well then that corresponds to an accepting computation in our nondeterministic machine. And so um that is also accepted. Let me make a bit more space because the conclusion still fits here. So fancy V the the language accepted by normal V as a verifier is thus this language. And so we've shown given an arbitrary language in NP we've shown that this language is also in VP and that of course proves that NP is a subset of VP.

9:29 Okay, This is in a way even easier, but let me just be slightly formal again to be a bit structured about the proofs once at least. So again given a language L in VP L over some alphabet what does it mean to be in VP? Well, it means there a polinomial time verifier.

10:16 Let's give it a name a for our language. And you can unfold the definition, but let's maybe not. Um, what we have to do here is to construct a nondeterministic machine.

10:40 Come on. Turing machine M. Uh, that simulates this verifier, which means it accepts the same language. Now, what does that mean to simulate A? I don't have the certificate. Well, Whenever A reads a bit from C, But what it means of course is that whenever there's a way where uh the we haven't spoken very clearly about how the verifier looks at as as a language I imagine it as a as a turing machine that has two input tapes one for the input and one for the a readonly bit for the verifier for the certificate say and so you can identify superficially in the machine when it reads one of the verifier bits or you could say the input is separated in a in a first part and a second part on the tape and you have to walk back and forth. That is a bit more annoying to track. But you can uh imagine that whenever you're reading a bit from the uh the part at the back that corresponds to C, you instead simulate that and insert both possible successor states that the machine would go depending on whether it reads a one or a zero there.

12:55 a cleaner way that is a bit more from the outside. This polomial time verifier A, it will have a certain runtime that you can know statically and so we know how many bits C can ever be used. So you might as well generate these up front as a first pre-processing step.

13:24 Let's say uh time a of n That's the time the machine is allowed to take on our specific input. So we first generate this string and then we simulate a completely on this.

14:22 It's cleaner because I don't need this assumption about what the verifier looks like. I can use it as a black box even if it has some complicated way of appending the two on the same tape. Uh this still works and it only needs the assumption that I somehow know the time or I can guess the time. Um so we're shifting the problem somewhere else. But uh both ways can be made to work with the right details uh underneath. Now of course um to finish off this constructs a nondeterministic Turing machine. I think in the second version is very obvious that it that just does the same thing. If there is any way to have this string there is a nondeterministic computation that outputs that 01 string and so on that 01 string A will have to accept this input XC. And so the machine M also accepts. And conversely, if there is no way for the machine to accept this input for any uh certificate string C, then M will also not find any accepting computation.

15:33 So the language accepted by this M will be our language L. And that concludes the proof. So in a way you could say it's a rather superficial rewriting of what the definitions mean either non-deterministic or the verifier few.

15:50 Uh so that's also entirely true. There's nothing deep behind it. But this verifier few makes it a bit easier to think about it. And it corresponds precisely to this the usual informal definition that NP means it's easy to check if a given solution is correct whereas uh finding a solution might be hard and P means also finding the solution is easy meaning poly time computable deterministically blah blah blah okay uh before before we move to the next chapter since this is kind of repetition for some of you many of you let's see how much on the next section we should pay attention to detail. Again, the question is a bit um asking you about what you've done for not from what we've discussed here. I haven't defined what boolean formulas are or what SAT is and all these things. Uh there will be some some more to come on this. So if you've not heard about this at all before, that's fine. I don't want to bore you to death. If you all have, that's the reason I'm asking.

18:10 and also like we're a small group ask if the question is unclear. Is it clear what this unsat problem should look like? There's a lot swept under the rug. Um, is it clear to all what boolean formulas look like?

18:49 I think it's a useful question to start the discussion. So, give you a sec and anyone still busy typing or thinking? Maybe the other way around.

19:17 Okay, you can still send it in. Uh, so um I guess several things could be true. Slider is taking longer than expected. Whatever that means.

19:45 Okay. Well, yeah, it seems to work either way. So, most of you are know correct. Nobody knows. Okay. It might reload at some point or not. There we go. Good. I already showed the reset just so that you also have the same in the live stream right so uh how would you certify that a formula is not satisfiable well that's precisely the problem it's not so easy uh you can easily sat certify that a formula is satisfiable by giving me an assignment of the variables and and I can go and check. It seems the other direction is a bit harder and indeed nobody really knows. It's true that a certificate would be uh conclusive if you just list all assignments but there's exponentially many. So for the question of innp this doesn't help. Uh also this shows that NP is not closed under complementation because the the complement problem the formulas that are satisfiable is an NP as we just argued just guess an assignment and check it works or give me an assignment I'll check it for you that works [snorts] but also we don't know maybe there is a clever way after all to encode non-satisfiability um and that's not that's rule not ruled out by anything we