Video 8-8: Summary

0:07 All that's left from this unit is a short recap and listing all the facts that uh we have established or you will establish in the this week's exercise sheet. Uh so the first part here is just some some known uh inclusions among these complexity classes. So they form a nice little uh sequence. P the nondeterministic poly time algorithms um are contained in those that uh allow some uh las vegas algorithm randomization but no incorrect outputs. Then one-sided error Monte Carlo and two-sided aromonteardo are even more general. And the unbounded error Monte Carlo was this PP class. Um but then that class has a overdone it. So in a way it's too powerful. It contains all of NP. So that that's going to be the that's going to be the line between potentially practically interesting and certainly practically not interesting. and uh you'll show a bit more about these one-sided error classes uh which is we'll discuss in the exercises um what the implications there are.

1:24 The big big news is it seems very plausible that P and BPP are actually the same because you can dandrandomize all of BPP. And so any problem any uh decision problem for which there is some randomized Monte Carlo algorithm with polinomial time you can actually find somehow uh with this non-constructive way a deterministic algorithm. uh but it's based on this assumption that uh we have heart functions according to this average circuit hardness. But if that is true, of course, all this hierarchy here collapses and they're all the same, which was one reason why we didn't spend a lot of time on these intermediate classes because there's good reason to believe at least from a complexity theory standpoint, they're not so interesting.

2:17 All right. So what what should you take from this apart from the lovely construction that won some people the Turing award? Uh you shouldn't try to solve NP hard problems if all your extra tricks is just randomization. That's very unlikely to to work. Or if it works, I mean come see me and it's probably a breakthrough. But yeah, more likely is there's some some something not going going through. uh but it still means this is this doesn't mean that randomness is useless. Um there's many things you can do with randomized algorithms where we don't know how to do it in deterministic ways in with the same same kind of qualities and guarantees. So in a way this this statement is is also restricted to what it really says namely uh decision problems only polomial versus exponential the big big uh dichotomy many things you can still do easier or faster randomized um and also uh there's some interesting problems at the boundary between complexity classes where exactly uh maybe this this question is why we can't make progress And we'll see some examples of that uh in the next unit.