(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].
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).
Not to be confused with DistPH, as in DistNP.
A middle-ground between classical and quantum proofs. Provers send (independent) probability distributions, or mixed states. After all proofs are sent, the verifier draws one sample from each proof.
If the proofs are allowed to be correlated, then the hierarchy collapses to just two levels as for QEPH.
Defined in [GY24] and shown to collapse to the standard definition of PH.
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].