Has the same relation to L that PP has to P.
Contains BPL and contained in DET [Coo85].
PLPL = PL (see [HO02]).
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 reducible in L to the problem of computing the determinant of an n-by-n matrix of n-bit integers.
Defined in [Coo85]. (Cook used NC1 reductions in his definition)
Contained in NC2, and contains NL and PL [BCP83].
Graph isomorphism is hard for DET under L-reductions [Tor00].
The corresponding function class turns out to be equal to GapL (see refs at GapL), that is, the determinant of integer matrices is GapL-complete.
Has the same relation to PL as SPP does to PP.
Contains the maximum matching and perfect matching problems under a pseudorandom assumption [ARZ99].
Contains UL.
Equals the set of problems low for GapL.