Publication:3768891
From MaRDI portal
zbMath0632.03035MaRDI QIDQ3768891
Publication date: 1986
probabilistic algorithms; combinatorial games; hierarchy; interactive proof systems; quantifier; oracle; complexity classes; Arthur-Merlin game
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
Related Items
Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, The strong exponential hierarchy collapses, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes, On helping by robust oracle machines, Does co-NP have short interactive proofs ?, Probabilistic quantifiers and games, Graph isomorphism is in the low hierarchy, Relativized Arthur-Merlin versus Merlin-Arthur games, Probabilistic complexity classes and lowness, Immunity and simplicity in relativizations of probabilistic complexity classes, Simultaneous strong separations of probabilistic and unambiguous complexity classes