Class Description

span-L: Span Logarithmic-Space

The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NL machine.

Defined in [AJ93], where it is also shown that span-L is a hard class in the sense that span-L is contained in FP if and only if FP = #P.

Span-L is contained in #P, and if span-L = #P, then NL = NP [AJ93].

Span-L is contained in FPRAS [ACJ+21].

Linked From

No class.