Class Description

SAPTIME: Stochastic Alternating Polynomial-Time

The class of problems solvable by a polynomial-time Turing machine with three kinds of quantifiers: existential, universal, and randomized.

Defined in [Pap83], where it was also observed that SAPTIME = PSPACE.

Linked From

AUC-SPACE(f(n)): Randomized Alternating f(n)-Space

The class of problems decidable by an O(f(n))-space Turing machine with three kinds of quantifiers: existential, universal, and randomized.

Contains GAN-SPACE(f(n)).

AUC-SPACE(poly(n)) = SAPTIME = PSPACE [Pap83].

[Con92] shows that AUC-SPACE(log n) has a natural complete problem, and is contained in NP ∩ coNP.

More about...


RG: Refereed Games

The class of problems solvable by a probabilistic polynomial-time verifier who can exchange a polynomial number of messages with two competing, computationally-unbounded provers -- one trying to convince the verifier that the answer is "yes," the other that the answer is "no." Note that the verifier can hide information from the provers. Public-coin RG amounts to SAPTIME, which equals PSPACE [Pap83].

RG is in EXP relative to any oracle [KM92]; they are equal, unrelativized [FK97b].

See also PCD, GPCD.

More about...