Average Time Complexity Classes
Jin‐Yi Cai, Alan L. Selman · 1995
We extend Levin's theory of average polynomial time to arbitrary time-bounds in accordance with the following general principles: (1) It essentially agrees with Levin's notion when applied to polynomial time-bounds. (2) If a language L belongs to DTIME(T (n)), for some time-bound T (n), then every distributional problem (L; ) is T on the -average. (3) If L does not belong to DTIME(T (n)) almost everywhere, then no distributional problem (L; ) is T on the -average. We present a hierarchy theorem for average-case complexity, for arbitrary timebounds, that is as tight as the well-known Hartmanis-Stearns [HS65] hierarchy theorem for deterministic complexity. As a consequence, for every time-bound T (n), there are distributional problems (L; ) that can be solved using only a slight increase in time but that cannot be solved on the -average in time T (n). We demonstrate that our definition is natural and is as justified for arbitrary timebounds as is Levin's definition for polyno...