Probabilistic quantifiers and games (Q1112019): Difference between revisions

A characterization of classical complexity classes (both deterministic and probabilistic) in terms of the ordinary quantifiers \(\exists\) and \(\forall\) together with a quantifier \(\exists^+\), which means roughly ``for most'', is given. Quantifier-swapping principles are presented that reduce many class-inclusion and hierarchy-collapse proofs to straightforward algebraic manipulations. Examples of theorems subsumed by such an approach are: (i) the containment of BPP in the second level of the polynomial hierarchy and (ii) the collapse of the Arthur-Merlin hierarchy to its second level. The paper also includes a chart of class- inclusion and oracle-based separation results.