Class Description

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.

Linked From

FNL/poly: Nonuniform FNL

Has the same relation to FNL as P/poly does to P.

Contained in #L/poly [RA00].

More about...


UCC: Unique Connected Component

The class of problems reducible in L to the problem of whether an undirected graph has a unique connected component.

See [AG00] for more information.

Equals L. [Rei04]

The corresponding class for directed graphs equals NL. On the other hand, none of that class's corresponding search problems are obviously FNL-hard.

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