A distribution 
is flat
if 
.
Flat distributions are commonly used in practice. For example,
the most frequently used model for undirected random graphs
without self-loops is 
with 
.
It consists of all graphs with vertex set 
in which vertices
are labeled and the edges are
chosen independently with probability 
, which is a
function of 
. So a graph 
with vertex set and
edges in this model occurs with probability
.
If we assume also that satisfies
for some fixed 
,
then 
is flat [Gur91a], since
.
Similar distributions for directed graphs are also flat for the
same reason [WB95]. Most of the NP-complete
graph problems have other
parameters as inputs-for example, rather than
taking just a graph as input, the input may be
, where 
is often
a bound on the
number of vertices
or the number of edges of some structure
the graph may have that the
problem is speaking of (clique, etc.).
So their distributions are flat.
Gurevich [Gur87] showed that
dealing with flat distributions to get
average-case completeness results
using p-time or ap-time reductions is impossible unless
.
Proof.a problem
with a flat distribution is complete
under ap-time reductions.
Then 
. Let
be an arbitrary decision problem in NTIME
for some polynomial .
For any 
, let 
.
Then 
is in NP. Define 
by
for the appropriate constant 
and 
if 
for any .
Then 
, which implies that
there is an ap-time reduction
from 
to 
. Hence, deciding whether
can be done by deciding whether 
.
Since is computable in time polynomial on -average,
computing 
can be carried out in time 
, due
to the particular selection of .
Also, 
for some 
and 
for all 
, where 
is polynomial on -average and
so 
again due to the definition of .
Thus, 
and so
for some polynomial 
. Since is flat,
there is a such that 
.
This implies that 
.
For reductions that are restricted to be one-one and length-preserving
within a polynomial (i.e., there is a polynomial such that,
for all , 
),
Wang and Belanger [WB95] showed that the
above incompleteness theorem is true
without any assumption.
We note that all the natural NP-complete problems are indeed
complete under such reductions.
Proof.to the contrary that
there were an ap-time reduction reducing DH1
to a problem with flat distribution ,
where is one-one and length-preserving within a polynomial.
Then 
is weakly dominated by with respect to .
Since is one-one, is weakly dominated by 
.
Since is flat, there is an 
such that
for all but finitely many .
Since is length-preserving within a polynomial,
there is a constant 
such that, for all 
, 
.
When 
is sufficiently large and greater than
, 
. So
.
But 
, which cannot
be weakly dominated by
, a contradiction.
