Class Description

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

Linked From

#L/poly: Nonuniform #L

Has the same relation to #L as P/poly does to P.

More about...


FNL: Function NL

Has the same relation to NL as FNP does to NP.

Defined by [AJ93], who also showed that if NL = UL, then FNL is contained in #L.

More about...


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

More about...


UL: Unambiguous L

Has the same relation to L as UP does to P.

The problem of reachability in directed planar graphs lies in UL [SES05].

If UL = NL, then FNL is contained in #L [AJ93].

More about...