Let 
be a distributional NP problem. If every other
distributional NP problem is p-time reducible to it, then
has no
ap-time algorithm unless every NP problem under any allowable distribution
has one. In order for such a complete problem to exist,
a certain condition on the
computability of allowable distributions is needed. If arbitrary distributions
are allowed, Wang and Belanger [WB93a] showed that no complete
distributional problems can exist with respect to one-one, p-time
reductions.
Note that all
the known NP-complete problems are
complete via one-one, p-time reductions.
Levin [Lev86] suggested that it is reasonable
to require distributions be p-time computable.
A real-valued function 
is p-time
computable [Ko83]
if there is a deterministic algorithm which, on every
string 
and every positive integer 
, outputs a finite binary
fraction 
in time bounded by a polynomial in 
and and such
that 
.
Clearly, if 
is p-time computable
then so is 
.
Blass showed that
the converse is not true unless 
(see [Gur91]).
With this fact in mind, we assume that in the sequel,
when we say that a distribution is p-time computable we mean that
both and are p-time computable.
There is strong evidence to believe, as hypothesized by Levin (see [Joh84]), that any ``natural" probability distribution is either p-time computable or else is dominated by one that is. One can indeed verify that all commonly used distributions do satisfy this property.
Denote by DistNP the class of all distributional NP problems
such that
for some p-time computable distribution 
.
(Other names such as RNP [Gur91] and DNP [WB93a] have
also been used to denote DistNP.)