Video 8-2: Probabilistic complexity classes: RP, co-RP

0:04 As a last addition to this introductory chapter on randomized complexity classes, I want to introduce a notion that we hadn't discussed before in detail and it it really makes more sense for decision problems only. Uh these are the one-sided error algorithms and it actually naturally happens if you design algorithms that they happen to be one-sided just as a matter of how they are constructed. Uh so let's look at a a simplistic example which is not a valid uh Monte Carlo algorithm but uh just to get the point across that one-sidedness is is natural in this case or can be natural. Uh if you look at the classic satisfiability problem a random algorithm randomized algorithm could just guess some assignment and then output whether the formula is satisfied. Now the probability for this guess to be correct depending on the formula could be very very small and so it will not be the error guarantee we require for Monte Carlo. But the point is still if the formula is unsatisfiable the probability to output incorrectly that it was is zero. There's no way that this algorithm will ever say yes it's satisfiable if it isn't because it always returns the true value of a formula.

1:23 And so at least in principle, this sounds like a a reasonable thing to exploit and you'll you'll uh see this in in this uh week's tutorial sheet uh that um it helps with amplifying probabilities.

1:45 The formal definition of the class of algorithms here is the one-sided error Monte Cargo algorithms. And we'll refer to the others then as two-sided error.

2:03 Just have that on the slide. Twosided error Monte Carlo are the unrestricted ones that we considered before. If we have a language, it's only really sensible for decision problems. The algorithm has to accept a word that is in the language with probability at least 1/2. And uh if the if the word is not in the language, it has to reject it no matter what randomness uh lays.

2:32 So acceptance is always correct but rejection could be a lie because you can falsely reject some of the words in the language. Why this way not the other way around? You can also define the uh one-sided aromonteard algorithm for the complement language and talk about that can also make sense depends on the specific problem what is more natural and there's corresponding complexity classes for those two uh categories as well. These are RP and CORP. RP is the set of languages where we have such a one-sided error Monte Carlo algorithm and co-p is just those where we have it for the complement language. And so again there's um these are somewhat similar to NP and co-enpense that also there's this asymmetry for NP. we would say uh there is a cert there is a certificate that makes the verifier accept an input if it is a true input whereas um if the word is not in the language then it can never output incorrectly yes it is uh it has to be it has to reject the input for every possible certificate so in that sense um RP and and NP fit together in in their their way of breaking symmetries Now, as you can um as you'll show in the the exercises, uh if you take a language that has a one-sided error Monte Carlo algorithm in of both kinds, uh one-sided error for L and L complement, you can turn that into one that is Las Vegas and um vice versa is easy.

4:19 Uh so in in a sense although superficially uh RP and co-p feel a bit like NP and co-enper uh because for for NP and co-enpor something you may have seen um we don't know really what happens if you take problems that are in NP and in co-enps they feel like they should maybe be in because they have a certificate both for yes and for no. So uh in both directions it's it's easy to certify that an instance is a a yes or a no instance if you're given the certificate but finding the certificate is is not clear in general. Um there these are the typical types of problems where we uh where we feel they live in between P and NP complete. These tend to be problems that are in this in this intersection. Uh but it's a big open problem if the intersection really is P or if there's something beyond. So you could say P is here.

5:32 Then we have NP around here and coenp around here. And whether this bit is empty, that's unknown. Whereas for the randomized equivalence of of NP, this is not the case. Right?