Video 2-5: Nondeterminism = Verification

0:01 What I've presented you in the last chapter is the historically first and maybe original version of defining P and NP, which also explains the names very nicely. So, P for polynomial, NP for non-deterministic polynomial. It is, however, the most confusing way to explain it and also the the least conducive of intuition. So, let me give you an equivalent one, which is also what I've um used to define things in this intuitive view at the beginning. Non-determinism is from the way we've defined Turing machines maybe arguably rather natural, but it's otherwise not at all natural. In particular, it's not anything to do with with uh parallel computation. It's not got anything to do with anything we can build. And an um equivalent characterization is this idea of certificates and verifiers. So, different way to define roughly the same thing is as follows. Again, I'm starting with a language. Think of this as a algorithmic decision problem, a yes-no question.

1:08 If I have some algorithm that gives is given an input from this potentially from this language that it should decide whether or not it's in the language, but it's also given a second thing, some random bit string or random I shouldn't say, some bit string, then such such an algorithm is called a verifier for L if the following funny thing holds, namely the language we want to decide is precisely the set of strings that I'm giving as input to my algorithm with some bit string, some certificate, where this accepts. In other words, if the word is in the language and Yeah, I would have hoped to have this spelled out.

2:02 If the word is in the language, then there must be some certificate so that our verifier accepts this word with the certificate X and I see.

2:27 On the other side, if our word is not part of the language, is a no instance, then we have the negation. There's no certificate so that this accepts.

2:42 Or in other words, for all certificates that you for all strings C, this rejects. So, there's an asymmetry here because there could be many certificates where the algorithm also says, "Nah, uh, I'm not going to accept this." The only point is, if this word is in the language, there must be one way to choose these bits so that that makes the verifier accept. In particular, for solving the problem, this is utterly useless because you have no way of finding this certificate, maybe. You just get told there is one. But, that's the definition, right? This defines a certain type of algorithm to be a verifier for this language L. Whether or not that is practically useful is besides the point. It's a definition. And you'll see how this ties to NP in a second. Um if the algorithm accepts, then we call C a proof or a certif- certificate for the fact that this string is in our language.

3:40 That's uh just the way um we speak about these about these beasts. Then um we can make further restrictions on this algorithm if uh the time that this this verifier takes is somehow polynomially bounded in the length of our our word then we call it a polynomial time verifier. And note that uh this condition here talks only about polynomial in the length of W, not talks doesn't talk about the length of this string C. But if I spend only a polynomial number of time steps, I can also just access at most a polynomial number of bits from this certificate. So, I might as well restrict the certificates to be polynomially bounded as well. If I have something longer, it's never going to be looked at. So, it's useless. So, you can without loss of generality assume that the certificates are small. So, in a way it's not entirely hopeless. You could try to go through all possible certificates and ask for each, "Does this make my machine accept?"

4:47 So, you can use the verifiers to to check effectively. But it's going to be slow because there's many certificates. Then based on this, you can define again a class of problems, VP, all those problems for which there is a polynomial time verifier.

5:06 Okay? Um let's do this for TSP again. Is TSP in this class VP? How would I know? Well, we have to check if we can build a verifier. What would a verifier for the TSP problem look like?

5:32 This W is some encoding of my instance. So, again, the number of cities, all the distances, and the threshold. >> And this threshold capital D. Now, um on top of that, I get this this bit string C that I'm somehow supposed to make good use of.

6:18 And I'm going to use these bits to tell me exactly which edges am I taking. And you have again a lot of freedom how to do that. Uh you could, for example, start at an arbitrary city, and then use the next bits to ask, "Do I go from this city to city one?" The next bit tells you yes or no. If yes, then you go to city one. If no, then you try the next. Do I go from my first from my current city to city two? Yes or no? The bit tells you. And each time you go, you now ask from that city onwards, and you only ask so that eventually you come back uh to make a cycle. I'm not going to Nobody enjoys writing this on a Turing machine, but there is some way to do it with levels of abstraction. So, um you can use this this certificate C as an encoding of one specific tour.

7:27 Now, if I have a specific tour, I can also imagine a Turing machine that follows the tour and adds up the distances. And then if I have the sum of all the distances along the tour, I can check it against D. That's also easy. So, with all these little steps combined, I've built a verifier for my TSP problem because I know for every instance where there is a tour that is at most length D, well, there is such a tour, so there must be some string C that encodes precisely this tour. And if I'm if somebody clever gives me that certificate string, I'm going to reconstruct the tour, add up the lengths, and determine they're at most D capital D. >> [snorts] >> Okay? So, this is a yes because this simple approach solves the problem. Building a verifier only means taking the certificate to encode one candidate solution and checking that it actually achieves this threshold that somebody claimed.

8:34 On the other hand, if I give a if I'm given a no instance where even the shortest tour is longer than this capital D, there's going to be no string C, no tour that someone can encode that is shorter because I'm assuming none exists.

8:49 Okay? This is maybe it's still not um getting needs getting used to, but it's much easier to think about than these weird nondeterministic Turing machines where somehow you're allowed to compute and at some points have several things that could happen.

9:08 Uh what we'll what we'll do next time is that indeed this is the same, it's just a different way of looking at things, but we'll almost always uh stay in this verifier view because it's it's much more natural to describe algorithms.

9:26 Okay. The proof uh I guess we'll do next time. >> The TSP is also only verifiable if you're using threshold, right? >> Yeah, that's right. all of this is um for languages, which means it's for decision problems only.

9:49 And verify, this is this is indeed is a a good point. So, here this is a bit sloppy, right? I shouldn't say TSP, I should say um the decision version.

10:05 That's a V of TSP. Uh the convention in complexity theory is to give problems to to use these names for problems to mean the decision version. But um yeah, I've not been formal about this part yet. That's to come. Uh so, we should be should be clear there. Um all of all of these classes only ever consider decision versions.