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].
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 NEXPNP ∩ coNEXPNP.
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.
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.