[34] Let T be a constructible time function. Show that for every time-constructible function t we have T (x)=2O(Kt(x)−K(x)+log n) iff T is polynomial time on mt

-average in L.A. Levin’s sense, that is, there exists a k such that 

x T 1/k(x)mt

(x)/l(x) < ∞.

Comments. Source: [L. Antunes, L. Fortnow, D. van Melkebeek, and N.V. Vinodchandran Theoret. Comput. Sci., 354(2006), 391–404].