Class Description

ZP•L: Zero-Error Probabilistic L with Two Way Access to Randomness

Has the same relationship to BP•L as ZPP has to BPP. More specifically, the set of languages with a log space, polynomial time Turing machine using a read only randomness tape such that on input x:

1. With high probability over the random bits used in the randomness tape will the machine correctly output whether x is in the language.

2. The machine will either wither correctly output whether x is in the language, or output 'unknown'.

Contains BPL [Nis93].

Contained in RNC since L is contained in NC and zero sided error is weaker than one sided error.

Contained in BP•L.

Linked From

BPL: Bounded-Error Probabilistic L

Has the same relation to L as BPP does to P. The Turing machine has to halt for every input and every randomness.

The randomness is read once. That is, each random bit is only given once and to be referenced again it must be stored in the working space. This in contrast to the two way randomness of BP•L.

Contained in SC [Nis92], PL, BP•L, ZP•L [Nis93], DET [Coo85], NC2 and P [BCP83].

More about...


BP•L: Bounded-Error Probabilistic L with Two Way Access to Randomness

Languages decided with two sided bounded error by a log space machine with a read only tape containing random bits. In contrast with BPL, the random bits can be read multiple times without storing them in working space.

For example, BP•L contains RNC1 since NC1 is contained in L. However, this reduction does not hold for BPL.

It is unknown if BP•L is contained in P [Nis93].

Contained in BPP.

Contains BPL and ZP•L.

More about...