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 to exist,
a certain condition on the
computability of allowable distributions is needed. If arbitrary distributions
are allowed, then no complete
distributional problems can exist with respect to one-one, p-time
reductions. In particular, Wang and
Belanger [WB93a] showed that
for any distribution 
, there is a distribution 
such that for any one-one, p-time reduction 
,
cannot be dominated by with respect to .
It is reasonable to focus on one-one
reductions, as all
known NP-complete
problems are indeed complete via one-one, p-time reductions.
Levin [Lev86] suggested that it is
reasonable
to require that distributions be p-time computable and it is also reasonable
to restrict attention to distributions with rational values (see
Lemma 3.2).
A function 
is p-time computable if
there is a deterministic algorithm that on input 
outputs
in time bounded by a polynomial in 
.
Gurevich [Gur91a] extended this notion
to real-valued functions (see also [Ko83]
regarding real-valued computational objects).
Clearly, if 
is p-time computable
then so is .
Blass showed that
the converse is not true unless 
(see [Gur91a]). 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.
Gurevich [Gur91a] showed that all p-time computable distributions are bounded above by nicely-behaved (``linearly presentable'') p-time computable distributions as follows.
Proof. is p-time computable, there is a
p-time computable finite binary fraction 
such that,
for all , 
, where
. Round down to
digits. Add 
if the last digit is 1.
This produces a binary fraction 
with at most 
digits,
and 
. Define by
, where 
is
the immediate predecessor of . Then 
has at
most 
digits and 
.
It follows that
.
Let be a p-time computable reduction and
an input distribution. If the induced output distribution
is p-time computable,
one might suspect that must also be p-time computable;
however, this was proven
false in [WB93a]. To see this, first
construct a set
with 
and,
for all 
, 
. Then
define a distribution such that, for almost all
(i.e., all but finitely many) ,
if 
and
otherwise.
Let be a finite binary fraction with
. Then, for almost all ,
iff has a 1 in the th position to the right
of the binary point (that is, what is usually called a decimal point,
except our fraction is binary).
Now define a distribution such that, for almost all ,
if
and 
otherwise.
Then is p-time computable but is not.
If were p-time computable, then there would be a p-time
computable , which would imply that 
,
which is a contradiction.
Define by 
. Then, for almost all 
,
.
