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 L as #P does to P.
#L is contained in the function class version of DET [AJ93]. In fact, the determinant is GapL-complete (see refs at GapL), where GapL consists of functions that are the difference of two #L functions.
See AC for definition.
Contains NL (hence also NC1). Contained in NC2. The complexity class DET also obeys all these containment relationships, but no containment is known in either direction between AC1 and DET.
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 solvable by a quantum Turing machine using O(log n) many qubits and polynomial time, with at most 1/3 probability of error.
Whether or not intermediate measurements are allowed does not change the resulting class [FR21].
Has the same relation to L as GapP does to P. (And therefore, has the same relation to #L as GapP does to #P.)
The determinant is GapL-complete [Vin91] [Dam91] [Tod91] ([MV97] also gave a new, self-contained proof). See also the corresponding decision class DET
See NC for definition.
Contains AC1 and DET, both of which contain NL. It seems we currently (as of this writing, 15 Jun 2022) do not know any problem in NC2 that's not known to be in AC1∪ DET (see this question).
Has the same relation to L that PP has to P.
Contains BPL and contained in DET [Coo85].
PLPL = PL (see [HO02]).