Class Description

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.

Linked From

No class.