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].
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).
(also called (NP,P-computable) or RNP)
A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.
(A,μ) is in DistNP if A is in NP, and μ is P-computable (meaning that its cumulative density function can be evaluated in polynomial time).
DistNP has complete problems [Lev86] (see also [Gur87]), although unlike for NP this is not immediate.
Any DistNP-complete problem is also complete for (NP,P-samplable) [IL90].