Class Description

PPSPACE: Probabilistic PSPACE

Same as IPP, except that IPP uses private coins while PPSPACE uses public coins.

Can also be defined as a probabilistic version of PSPACE.

Equals PSPACE.

Defined in [Pap83].

Linked From

Almost-PSPACE: Languages Almost Surely in PSPACEA

The class of problems that are in PSPACEA with probability 1, where A is an oracle chosen uniformly at random.

Almost-PSPACE is not known to equal PSPACE -- rather surprisingly, given the fact that PSPACE equals BPPSPACE and even PPSPACE.

What's known is that Almost-PSPACE = BPexpā‹…PSPACE, where BPexpā‹… is like the BPā‹… operator but with exponentially-long strings [BVW98]. It follows that Almost-PSPACE is contained in NEXPNPcoNEXPNP.

Whereas both BPexpā‹…PSPACE and BPPSPACE machines are allowed exponentially many random bits, the former has a reusable record of all of these bits on a witness tape, while the latter can only preserve a fraction of them on the work tape.

More about...


BQPSPACE: Bounded-Error Quantum PSPACE

Equals PSPACE and PPSPACE.

More about...


IPP: Unbounded IP

Same as IP, except that if the answer is "yes," there need only be a prover strategy that causes the verifier to accept with probability greater than 1/2, while if the answer is "no," then for all prover strategies the verifier accepts with probability less than 1/2.

Defined in [CCG+94], where it was also shown that IPP = PSPACE relative to all oracles. Since IP is strictly contained in PSPACE relative to a random oracle, the authors interpreted this as evidence against the Random Oracle Hypothesis (a slight change in definition can cause the behavior of a class relative to a random oracle to change drastically).

See also: PPSPACE.

More about...