Distributions that are p-time computable can be dominated (with respect to p-time computable functions) by uniform distributions, which is an important property for proving completeness results. Levin [Lev86] first proved this property using a ``perfect rounding" technique that is interesting in its own right (see [Gur91a] for an exposition). Gurevich [Gur91a] provided a different and easier proof, and based on that Wang and Belanger [WB95] showed that if the distribution is not too small, it will also dominate the same uniform distribution within a constant factor.
Proof Sketch.
be the linear presentable
distribution that bounds 
, as guaranteed by Lemma 3.2.
Let 
be the shortest binary string such that
.
Then 
.
Now let 
be the position of the leftmost digit
that is 1 in the binary fraction produced by
a p-time algorithm that computes 
on input
.
Then 
.
Let 
, where 
.
