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
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.
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.
A language if there are functions and such that for all strings :
Thus, for any prime and natural number , . Moreover, FLModL = FLGapL [AV04].
Defined in [AV04].
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.