Probabilistic quantifiers, adversaries, and complexity classes: An overview. (English) Zbl 0632.03035

Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 383-400 (1986).
[For the entire collection see Zbl 0591.00015.]
The paper deals with inclusion relations among several complexity classes arising from probabilistic algorithms, combinatorial games and interactive proof systems. A uniform description of such classes is achieved by applying to polynomial-time predicates the usual (polynomially bounded) existential and universal quantifiers, together with an additional quantifier, roughly meaning “for most”. This approach yields easier proofs of some class-inclusion, and hierarchy- collapse results.
Reviewer: D.Mundici


03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)


Zbl 0591.00015