zbMATH — the first resource for mathematics

Probabilistic quantifiers vs. distrustful adversaries. (English) Zbl 0647.68052
Foundations of software technology and theoretical computer science, Proc. 7th Conf., Pune/India 1987, Lect. Notes Comput. Sci. 287, 443-455 (1987).
[For the entire collection see Zbl 0625.00019.]
Probabilistic complexity classes are studied in terms of a notion that focusses on alternating quantifiers. It is shown that classes obtained by “Arthur-Merlin” games and by “interactive proof systems” can be expressed by such alternating quantifiers. Several new relationships between (relativize) probabilistic complexity classes are revealed.
Reviewer: U.Schöning

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity