It is desirable to have a general hierarchy theorem in the framework
of Definition 2.1 that is as tight as
the Hartmanis-Sterns hierarchy. To achieve such a result, it is necessary to
distinguish among 
on average for different values of 
.
One way to do so is to define a function 
to be 
on average if
, and so we would be
comparing to 
rather than 
for arbitrary
.
A function 
could then be said to be 
on average if 
for some 
on average function , i.e., if
.
This would then make
a distinction between a function being
on average and 
on average.
However, since an algorithm that
solves a decision problem can be given look-up
tables to speed up computation
on any given finite number of inputs,
we would again have AvDTime() = AvDTime().
Let 
,
where 
is the conditional distribution of 
on 
.
To remove dependency on any finite number of inputs,
it is natural to require that, for all , 
.
Let 
.
It follows
that 
.
Cai and Selman [CS95] proposed the
following definition.
By the hierarchy result of Geske et al. [GHS91],
we immediately get a strong hierarchy result
under Definition 5.2. That is,
for time-constructible and monotonic increasing functions
and , if 
, then there is a
language 
such that for any distribution , is
computable by a deterministic Turing machine in time
on -average, but no deterministic Turing machine can
computes in time on -average. Note that this
hierarchy result is independent of distributions.
Clearly, any distributional decision problem that is computable in
average polynomial time under Definition 5.2 is
in AP. While the converse is not true,
Cai and Selman [CS95] showed that
there is a partial converse. That is, under a fairly reasonable
condition on the distribution , called condition W,
a distributional decision problem is
computable in average polynomial time under Definition 5.2
if and only if it is in AP. A
distribution is said
to satisfy condition W if
on all
strings of length at least n has a lower
bound of 1/p(n) for some polynomial p.
Thus, the theory of reducibility
is preserved for average polynomial time under
Definition 5.2
when restricted to distributions that satisfy condition W.
However, if condition W is not satisfied, then
Definition 5.2 may fail to
preserve reducibility for average polynomial time. In particular,
Belanger and Wang [BW96] constructed two
distributional decision problems 
and 
,
with p-time computable and 
, where
does
not satisfy condition W
but does,
such that is ap-time reducible to
and is solvable in average polynomial time
under Definition 5.2, but is not.
Thus, if condition W
is not enforced, a ``hard'' problem can
be reduced to an ``easy'' one under Definition 5.2.
