Cai and Selman (1995) proposed a general definition of average computation time that, when applied to polynomials, results in a modification of Levin's notion of average-polynomial-time. The effect of the modification is to control the rate of convergence of the expressions that define average computation time. With this modification, they proved a hierarchy theorem for average-time complexity that is as tight as the Hartmanis-Stearns hierarchy theorem for worst-case deterministic time. They also proved that under a fairly reasonable condition on distributions, called condition W, a distributional problem is solvable in average-polynomial-time under the modification exactly when it is solvable in average-polynomial-time under Levin's definition.
Various notions of reductions, as defined by Levin and others, play a central role in the study of average-case complexity. However, the class of distributional problems that are solvable in average-polynomial-time under the modification is not closed under the standard reductions. In particular, we prove that there is a distributional problem that is not solvable in average-polynomial-time under the modification but is reducible, by the identity function, to a distributional problem that is, and whose distribution even satisfies condition W.