Video 8-1: Probabilistic complexity classes: ZPP, BPP, PP

0:03 In the next unit, we'll look at uh complexity classes for randomized algorithms. For the other sections or the other big parts in the module, I I swapped the order and first talked about algorithmic techniques and then at the end as kind of a more of an afterthought, um what are techniques to show that you can probably not apply what I've just shown you. uh here I don't want to flip it around and first talk a bit about what is possible or maybe not possible with randomization.

0:33 Uh so um I'm hoping to show some relatively advanced theor complexity theory bits in here which at some point I might um only sketch some details because it it leads us too far. Um but there's there's beautiful intuitions to be taken from them. So I think it's it's worth the journey. Uh and also there's some some strong but unproven hypothesis uh with practical implications. I think let's start from from the basics. Um the question that we ask here is uh how powerful is randomness? And we've seen examples like the median selection where it's provably uh improving but it's not so clear how general this is and by how much it improves. The bigger theme in the in the unit in this module is P versus NP polomial versus well say exponential. Um can randomness play in this league of differences?

1:38 Um and in particular from a complexity theory perspective, the question is can you uh solve more decision problems or more problems in general with randomization in polomial time than without.

1:55 And so certainly we'll essentially look only at decision problems here and try to build up a a bit of a a cleaner um uh complexity view on on on these things and the first step towards that is to define um some complexity classes for the types of algorithms we've already seen with polomial running time. Um this not that much uh surprising to be there but let's do it uh properly. Uh first of all uh we talk about decision problems only which equivalently are just languages subsets of sigma star if we decide that's our um universal input alphabet. And uh then because we're talking just about accepting words or rejecting words from this language, the only three outputs that we'll use is zero for reject, one for accept, and the question mark still is there as one option of saying I'm I kind of my computation failed. I can't tell you whether it's in the in the language or not.

3:10 um we'll I think we'll we'll yeah for most of it not restrict how many random bits algorithms take. So they should be assumed to take a random bit in every computational step. At least that's the worst case that's possible.

3:29 And with that we can uh define several several potential classes of problems. The first one is called uh ZPP the zero error probabilistic poly time algorithms or languages. It's a set of all languages for which there is a Las Vegas algorithm. Yeah. Okay. Poly time is of course important. Um but that's uh that's going to be part of all these definitions. So just again to remind you uh there's that's the the um weaker form but um we assume this always terminating variant. So there's some uh polomial upper bound for the running time and the success probability is at least 1/2 and also uh if the algorithm outputs not the right answer then it must output a question mark. Okay so it cannot say a wrong thing. Las Vegas that's uh ZPP.

4:30 Then uh similar name but different beasts is BPP the bounded error probabilistic poly time problems. It's the set of all languages where we have a Monte Carlo algorithm but crucially of the bounded error type. I keep stressing this but you've seen it when we talked about chof bounds now that these are really different. So again uh just to have that on the slide again polomial time always terminating and uh there has to be an epsilon specific to the algorithm independent of the inputs. So that uh the probability for for every input this is there's a for all x uh in sigma star here uh for all inputs you output the right answer with probability at least half plus epsilon. It's the same same as before um just repeating the definition. Uh we have a third type of algorithm namely the unbounded error Monte Carlo algorithms. So to uh make things complete let's also define a class for those that's called PP just probabilistic poly time.

5:39 Um I don't know if people historically first looked at those. It sounds maybe like the most most natural class. You just say uh it's any algorithm that has a polomial running time and it should be correct in strictly more than half of the cases. Maybe that's the most natural if you don't think about it. Um but you'll see this uh this is not a good class.

6:04 Uh those are the the three main classes um we'll look at. Now we can um make a few assumptions to make life a little more convenient. um we only bound the running time in terms of polomial no matter how big the polomial is. So repeating an algorithm a few times is fine. In particular for the bounded error algorithms we already know just some logarithmic number of rounds will actually boost you to with high probability. Um but what we'll assume is that we have a success probability of 2/3 if nothing else is is stated. Uh that will make one or few uh one or two calculations easier later. That's true for BPP and and ZPP. We know for PP for the unbounded error algorithms we can't actually make such an assumption and stay polomially time in polomial time at least not with a simple repetition. That's what we showed in the last section. But here comes the the real bummer for PP.

7:16 Uh PP contains all problems in NP. And because we're uh while we're at it, it also contains all problems in co-enp. So uh this seems really strange and it's just an indication that uh unbounded error is is useless. You can do almost anything with that which on the flip side means just because you have a bounded error unbounded error algorithm doesn't help you at all. Uh but let's let's nevertheless prove this because I think this is a a somewhat still somewhat surprising statement, right? Uh we're supposed to be able to do anything that a non non-deterministic algorithm does with a Monte Carlo algorithm. H and if you if you think about it, you know, we always said non-deterministic means there's a single potentially just a single computation that accepts and all the others reject. That's far away from accepting with more than half of the computations. How's that gonna going to be possible? Right? Seems um seems hard to prove. Um the trick is that we can can use the theory of um what we learn what we know about NP uh to help us here.

8:40 uh first of all the the class PP certainly allows any kind of polomial pre-processing right because that's so if I'm if that somehow helps me I can take my problem and apply a polinomial time algorithm first to that problem and then solve what comes out and that's going to stay in PP if the overall thing has a PP solution that's a lot of piece um because we're just adding a polomial time so in particular uh we can apply uh polinomial time reductions to our problem.

9:59 So in particular we can say um that L must polomial time reduce to the satisfiability problem because that that old friend was nplete. So it suffices to solve SAT with PP. Then I've solved all of NP, right? Uh, it's the same old same old story and um the way we'll do this will will actually be general enough that you can do the same with co-enp hard problems. We haven't spoken a lot about co-enp but uh it's kind of the flip side. So the the general uh the counterpart to satisfiability would be the tortology problem. Uh given a boolean formula decide whether it's a tautology. That's true for any variable assignment.

11:27 and we can use that to show the other inclusion but we'll focus on sat here. So let's try to do this. Um we have to give an algorithm unbounded error Monte Carlo algorithm for SAT.

12:05 So how do we do this? Um given a formula let's say it has length n and k variables um first step is you're going to do something random, right? So let's do something random. I just generate a random assignment I'm just going to call it V from the variables And this doesn't need much explanation. You just pick K random bits for that.

13:46 if B makes A true. I true. then we output a one because we've obviously proven that the formula is uh satisfiable and otherwise that's the tricky bit right what are we going to do now otherwise we flip a biased coin and output whatever that coin says And the trick is to choose this probability, right?

14:24 And it's essentially 1/2, just a tiny tad less. Okay, plus one. Let's make this a bit less absurd. So, I'm going to take a coin that's ever so slightly bent towards coming up as zero.

14:46 So it's strictly less than 1/2 but ever just so slightly. And the claim is um number one what's the running time of this? Let's do that first.

15:09 Um this is linear in K. This is linear in N I guess or at least polomial in in N. And this is maybe even constant expected at least we've seen the discussion of how to generate things like that. But let's be generous and maybe say K because you're probably going to need K bits to do that simulation doesn't matter much. Um certainly polomial it's actually even even linear but so that's fine. Uh how about the correctness? We have to show that we output the right answer.

16:07 The probability that a outputs phi needs to be the same as a is satisfiable. This is a claim strictly greater than 1/2. That's what we claim.

16:28 And so we'll do a case distinction. If by is insert then we'll always output um we'll always output that right um no sorry forget it it's not um but if if fi is satisfiable at least one satisfying assignment exists for the variables x1 up to x k. Now in the worst case there's a single one. That's the that's the only thing we can say but still the the probability that uh step two succeeds is at least one over 2 to the k because there's two to the k in assignments in total and at least one has to be satisfying. Okay.

17:27 Um so then let's let's analyze with the overall failure probability that um a output zero which is which is wrong in this case. So well the output zero we must fail in step two right. Um, we have a a nice let me um let me write for this v of pi equals 1. Okay, because it's annoying not to have a notation. It's it's just we need some notation for a formula under a variable assignment. What's the value of that thing? um I don't want to write these variable substitution in in square brackets all the time.

18:28 So it's the probability that our random assignment that we pick says this thing is false. But if if that's the case, then we continue with step three, which is flipping this random coin. And uh we do this with fresh random bits. So it's independent of the previous thing.

18:53 So that has also uh to be zero. I guess here we use independence. But that's harmless because we're generating these we're we're making them independent by running step two and three with um with disjoint random bits.

19:08 Okay. Uh then we just have to calculate and I'm running out of time. So this was the counter probability for this. So can't be uh less than this. And this one was by choice our counter probability for the other thing. And now we just find that this is less than 1/2. Right? I do the math and and multiply it multiply it out.

19:43 Um so we if the formula is satisfiable we reject it with a probability less than 1/2. And the second case luckily it's easy. If the formula is satisfiable then the probability that um our random assignment satisfies it is zero.

20:19 And so the overall probability that this one is wrong that it accepts um it's going to be one for namely the output that we have to do step three and then again our our P the probability that this is one this time and that's uh p which is less than 1/2. So again the uh probability that we output the wrong result is less than 1/2 in both cases which means the overall claim is is is shown namely the probability that we output the right thing And that was what we wanted to show. So that if if you had any doubts before this proof, uh this certainly drives home that PP is is not interesting. You need bounded error Monte Carlo algorithms for any kind of interesting uh results both practical and for the error probability and and in theory for having interesting complexity classes.