Class Description

GapL: Gap Logarithmic-Space

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

Linked From

#L: Sharp-L

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.

More about...


DET: Determinant

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.

More about...


ModL: ModL

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

More about...


SPL: Stoic PL

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.

Contained in C=L and ModkL.

Equals the set of problems low for GapL.

More about...