Class Description

FPRAS: Fully Polynomial Randomized Approximation Scheme

The subclass of #P counting problems whose answer, y, is approximable in the following sense. There exists a randomized algorithm that, with probability at least 1-δ, approximates y to within an ε multiplicative factor in time polynomial in n (the input size), 1/ε, and log(1/δ).

The permanent of a nonnegative matrix is in FPRAS [JSV01].

Linked From

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

More about...