[40] Use the uniform complexity of Exercise 7.1.7.

We consider a time–information tradeoff theorem for resource-bounded uniform complexity. Let fi = n1/i, for i = 1, 2,... . Construct a computable infinite sequence ω and a set of total computable, nondecreasing, unbounded functions {ti}, where the ti’s are computably enumerated as t1, t2,..., such that the following hold:

(a) For all i > 1, we have ω ∈ CU [fi, ti, ∞], where CU [·] is defined in Exercise 7.1.7.

(b) For all i, ω ∈ CU [fi, ti+1, ∞].

Comments. Source: [R.P. Daley, J. Assoc. Comp. Mach., 20:4(1973), 687–695]. Daley proved a more general statement with a general characterization of {fi}.