To study average-case hierarchies in the framework of
Definition 2.1, a finer distinction between average time,
namely, not just between average polynomial and super-polynomial,
is needed. Recall that
the notion of average polynomial time is defined, on purpose, not to
distinguish 
time from 
time,
to guarantee machine and encoding independence.
For a fixed computation model, however, we can distinguish
time from time.
Ben-David et al. [BCGL92]
suggested a direct generalization of Levin's definition.
Levin's definition can be rephrased as saying that a function 
is polynomial on average if there exists a linear on average
function 
and a 
such that, for all 
, 
, whe
re is linear on average if
.
Ben-David et al. defined
a function to be 
on average if 
for some
linear on average function . This can be rephrased as follows.
For any function 
, let
.
Denote by AvDTime
the class of all distributional decision
problems 
such that 
can be decided
by a deterministic algorithm whose
running time is on 
-average.
Since the definition of linear on average does not
make the distinction
between 
on average and cn
on average for any
constant 
,
T(
)
on average is the same as 
on
average for any function and any constant 
.
Thus, it is not possible to get very fine separation results.
When is polynomially bounded, however,
the distinction between time and time also does not
exist for worst-case deterministic time because of
the linear speedup theorem. It is therefore possible to prove an
average-case hierarchy result as tight as in the worst case.
Cai and Selman [CS95] obtained such a
result when the time functions involved
are restricted to be logarithmico-exponential.
The class 
of logarithmico-exponential (log-exp, in short)
functions, first studied by Hardy [Har11],
is the smallest class of functions 
containing every constant function 
and the identity
function 
such
that if 
and 
are in 
, then so are 
,
(i.e., 
),
and 
(if is eventually positive).
It follows that 
, 
,
and 
are also in .
It was shown in [Har24] that every function in
is either
eventually positive or eventually negative or identically zero.
It follows that every function in is eventually monotonic
by the fact that is closed under differentiation.
Define 
(
) and 
.
It was shown in [Har11] that
if 
tends to infinity, then there is a constant
such that 
as well as
.
A function is a log-exp time function if for some
and for all 
,
.
It is easy to see that almost all commonly used time functions are
log-exp [CS95].
(There are some exceptions, e.g.,
the time function 
is not log-exp.
)
Proof Sketch.
Let 
and
.
Let 
.
Then we have 
, and so 
.
Also, 
and 
. Let
. It follows that
. Thus, there is a language 
such that any Turing machine that
accepts 
requires more than 
steps for all but finitely
many inputs . Clearly, 
for every distribution 
.
Let 
be an integer such that 
. Then
is eventually monotonic decreasing.
It follows that, for all 
and all sufficiently large ,
, and so
.
Since is eventually monotonic increasing,
for sufficiently large .
Let 
, then 
is log-exp.
So there is a constant such that 
.
For this , there exists an 
such that when
, 
is defined,
and we denote it by 
. Define 
for 
. Then
but 
.
Let 
.
It follows that 
.
When is exponential or higher, the fact that there is no
distinction between and in Definition 5.1
can produce counterintuitive results.
For example, it is easy to see that
since 
[CS95],
but by the hierarchy result in [GHS91],
there is a language in DTIME
that requires more than 
time to compute on all but
finitely many inputs. Some hierarchy results, however,
can still be obtained for general time bounds
under uniform distributions [BW95]. In
particular, Belanger and Wang [BW95] showed that
if 
for
some 
, where and are time-constructible, then
there exists a distributional decision problem
with
for the
appropriate
such that
.
A slightly tighter hierarchy can also be obtained under nonuniform
distributions [SY96].
