PP is overpowered

(You can watch the video version of this post on YouTube.)

Now there are all kinds of different complexity classes for, uh, probabilistic computation. We’ll get into some reasonable ones another time, but here’s one that sounds - like a good idea, maybe, but is really powerful in a way that’s just not reasonable.

So PP is the class of problems that can be solved in Probabilistic Polynomial time in the sense that we must accept YES instances with probability strictly larger than $\frac12$ and and No instances with probability at most $\frac12$. (Sometimes the definition also says strictly less than \frac12 here, but that ends up being equivalent and this way my story is better.)

I don’t know what your intuition is - is this a powerful class? - well, let’s solve SAT real quick - we’ll do a pro gamer move here, you see: with probability one-half, we just say YES. Uh, really. And otherwise, we pick one random assignment and return whether it satisfies the instance. Algorithm’s real fast. See, if the formula is UNsatisfiable, this second step cannot say yes and the acceptance probability is just the blanket 50% from the start; if the formula is satisfiable, we now say yes with an additional positive probability. QED. You can futz around with this a little bit to make it strictly less than $\frac12$ in the unsatisfiable case, but I like how clean this version of the algorithm is.

And here’s the problem with PP: we followed the rules, but we didn’t really do a good job doing anything .. useful. The difference in probability between the cases can be arbitrarily small, so you can’t efficiently amplify it to something reliable. THAT’s something to watch out for in probabilistic computation: amplification. And PP’s relation to other complexity classes actually is kind of interesting, but I’ll let you look that up on your own.