Zachos, Stathis 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 Cited in 13 Documents MSC: 03D15 Complexity of computation (including implicit computational complexity) 68Q25 Analysis of algorithms and problem complexity 68Q05 Models of computation (Turing machines, etc.) (MSC2010) Keywords:quantifier; hierarchy; oracle; Arthur-Merlin game; complexity classes; probabilistic algorithms; combinatorial games; interactive proof systems Citations:Zbl 0591.00015 PDFBibTeX XML