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.
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].
The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. They can have polynomially many rounds of interaction. Given the verifier's algorithm, at the end:
Defined in [GMR89], with the motivation of providing a framework for the introduction of zero-knowledge proofs (see the class ZK). Interestingly, the power of general interactive proof systems is not decreased if the verifier is only allowed random queries (i.e., it merely tosses coins and sends any outcome to the prover). The latter model, known as the Arthur-Merlin (or public-coin) model was introduced independently (but later) in [Bab85], and a strong equivalent (which preserves the number of rounds) is proved in [GS86]. Often, it is required that the prover can convince the verifier to accept correct assertions with probability 1; this is called perfect completeness.However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
First demonstration to the power of interactive proofs was given by showing that for graph nonisomorphism (a problem not known in NP) has such proofs [GMW91]. Five years later is was shown thatIP contains PH [LFK+90], and indeed (this was discovered only a few weeks later) equals PSPACE [Sha90]. On the other hand, coNP is not contained in IP relative to a random oracle [CCG+94].
The verifier for PSPACE only uses logarithmic space when given two way, read only access to its randomness. On the other hand, given only read once access to its randomness, a log space verifier can only verify languages in P [Sha90]. Further, a log space verifier with read once access to its randomness can verifier any language in P [GKR15]. See BPL vs BP•L for a comparison between read once and read multiple access to randomness.
Has the same relation to RNC as NC1 does to NC. And the same relation to NC1 as RP does to P.
Contained in BP•L.
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'.
Contained in RNC since L is contained in NC and zero sided error is weaker than one sided error.
Contained in BP•L.