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).
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.
Has the same relation to E as AvgP does to P.
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].