A difficulty among completeness proofs for the average case complexity
is that it is hard to maintain
the domination property for probability distributions. In general,
if the size of the output of a reduction is
a linear growth of the size of its input, then it may damage the domination
property.
For example, if we were to reduce the
halting problems to a problem 
in an effort to show that
is complete,
we would try to find a reduction 
such that 
.
If the reduction transforms 
to 
such that
has a parameter 
with 
for
some 
and 
being an irreducible factor of 
,
then cannot dominate 
with
respect to .
The only possibility left in this connection
is for to satisfy 
.
A dynamic binary coding scheme was introduced
by Gurevich [Gur91] to meet
this requirement, which will be used throughout this section.