Class Description

RNC1: Randomized NC1

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.

Linked From

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...