Probabilistic complexity classes and lowness

摘要

General properties and proof techniques concerning probabilistic complexity classes are discussed. Two versions of probability amplification lemmas are presented wich connect probabilistic complexity classes with nonuniform classes. The “quantifier simulation” technique is introduced which allows assertions that hold with high probability to be expressed by two alternating quantifiers. Quantifier simulation is the key technique to prove several lowness properties of probabilistic complexity classes.