scientific article
From MaRDI portal
Publication:3768891
zbMath0632.03035MaRDI QIDQ3768891
Publication date: 1986
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
probabilistic algorithmscombinatorial gameshierarchyinteractive proof systemsquantifieroraclecomplexity classesArthur-Merlin game
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (15)
On helping by robust oracle machines ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ 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 ⋮ On the power of parity polynomial time ⋮ Rational analysis, intractability, and the prospects of `as if'-explanations ⋮ Immunity and simplicity in relativizations of probabilistic complexity classes ⋮ Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy ⋮ Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy ⋮ The strong exponential hierarchy collapses ⋮ Probabilistic complexity classes and lowness ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes ⋮ Computational complexity of multi-player evolutionarily stable strategies
This page was built for publication:
