Class Description

Almost-PSPACE: Languages Almost Surely in PSPACE^A

The class of problems that are in PSPACE^A 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 = BP^exp⋅PSPACE, where BP^exp⋅ is like the BP⋅ operator but with exponentially-long strings [BVW98]. It follows that Almost-PSPACE is contained in NEXP^NP ∩ coNEXP^NP.

Whereas both BP^exp⋅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.

Linked From

No class.