Probabilistic Complexity Classes and Lowness
Uwe Schöning · 1987
In this overview properties and proof techniques concerning general probabilistic complexity classes are discussed. Two versions of probability amplification lemmas are presented, which connect probabilistic complexity classes with nonuniform classes. The "quantifier simulation" technique is introduced which allows to express assertions that hold with high probability by two alternating quantifiers. Quantifier simulation is the key technique to prove several lowness properties of probabilistic complexity classes.