Class Description

AvgP: Average Polynomial-Time

A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.

A function f, from strings to integers, is polynomial on μ-average if there exists a constant ε>0 such that the expectation of fε(x) is finite, when x is drawn from μ.

Then (A,μ) is in AvgP if there is an algorithm for A whose running time is polynomial on μ-average.

This convoluted definition is due to Levin [Lev86], who realized that simpler definitions lead to classes that fail to satisfy basic closure properties. Also see [Gol97] for more information.

If AvgP = DistNP then EXP = NEXP [BCG+92].

Strictly contained in HeurP [NS05].

See also: (NP,P-samplable).

Linked From

AVBPP: Average-Case BPP

Defined in [OW93] to be the class of decision problems that have a good average-case BPP algorithm, whenever the input is chosen from an efficiently samplable distribution.

Note that this is not the same as the BPP version of AvgP.

More about...


AvgE: Average Exponential-Time With Linear Exponent

Has the same relation to E as AvgP does to P.

More about...


(NP,P-samplable): Average NP With Samplable Distributions

See AvgP for basic notions of average-case complexity.

(NP,P-samplable) is the same as DistNP, except that the distribution μ only needs to be samplable in polynomial time. μ's cumulative density function does not need to be computable in polynomial time.

Any problem complete for DistNP is also complete for (NP,P-samplable) [IL90].

More about...