There is yet another approach, which studies
average-case hierarchies under an entirely different
average-case measurement. Reischuk and
Schindelhauer [RS93] suggested measuring
average-case complexity with respect to
the ranking of the input distribution
by decreasing weights instead of individual values.
Two distributions 
and 
are
said to have the same rank if, for all 
and 
,
iff 
.
The ranking function
of a distribution is defined by
.
This definition depends only on
, and not on
the individual values of each distribution with the same rank.
It turns out to be powerful for obtaining tight hierarchy results.
In fact, it delivers an optimal
separation result, namely that separation of average time complexity
classes can be obtained under the assumption
that 
[RS93].
However, it is not known whether there are natural NP-complete problems under commonly used distributions that are solvable in average polynomial time with respect to the rank of the distributions.
Belanger and Wang [BW][BW95] provided a comparison
between the two notions of 
on average under Definitions 5.1
and 5.3.
By definition, a function
being on average with respect to ranking already implies that it
is on -average for any with the same ranking.
Thus, it is the other direction that attracts attention.
An ideal connection between these two notions of average time would be
a result of the form: 
is solvable in time on
-average
exactly when 
is solvable in
average time
with respect to ranking.
This, however, is impossible since it will imply the
existence of a hierarchy for AvDTime(
) tighter than is possible.
Therefore, any connection between these two notions will have
to be of a weaker form. As we have seen before,
every distributional problem with a
samplable distribution is
reducible to a distributional problem with a uniform distribution.
Thus, one would like
to know whether a distributional decision problem
, with 
being p-rankable,
can be ``reduced'' to a problem 
, where
denotes the default uniform distribution, such that
if is solvable in time on -average,
then is solvable in time 
on
-average for some polynomial 
. This was shown to
be the case by Belanger and Wang
[BW][BW95].
In particular, they
showed that
if 
is a distributional decision problem
with a p-time computable ranking function ,
and 
is solvable in time on -average,
then is solvable in time 
on
-average,
where and 
are polynomials depending on .
To guarantee that is in NP when 
is in NP,
one would like
to be length-preserving.
Using a standard randomized reduction,
it was shown in [BW][BW95]that there is a complete problem for 
under a
randomized reduction, where is a length-preserving ranking function,
such that if is solvable
in time on -average, then
is solvable in time 
on -average,
where is a polynomial time bound for computing
.
Hence, does not provide
harder problems than DistNP.
