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 NC¹ reductions in his definition)

Contained in NC², 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 ${\displaystyle L\in {\mathsf {ModL}}}$ if there are functions ${\displaystyle f\in {\mathsf {GapL}}}$ and ${\displaystyle g\in {\mathsf {FL}}}$ such that for all strings ${\displaystyle x}$:

• There exists a prime ${\displaystyle p}$ and a natural number ${\displaystyle \alpha }$ such that ${\displaystyle g(x)=0^{p^{\alpha }}}$.
• ${\displaystyle x\in L}$ if and only if ${\displaystyle f(x)\equiv 0(\left|g(x)\right|)}$.

Thus, for any prime ${\displaystyle p}$ and natural number ${\displaystyle \alpha }$, ${\displaystyle {\mathsf {Mod}}_{p^{\alpha }}{\mathsf {L}}\subseteq {\mathsf {ModL}}}$. Moreover, FL^ModL = FL^GapL [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 Mod_kL.

Equals the set of problems low for GapL.

More about...