[25] Let t(n) be computable in time t(n), t

(n) = ct(n) log t(n)+

c, for some constant

c. For set A, string x, and some constant

c, prove:

(a) ict

(x : A) ≤ Ct

(x) +

c, and

(b) ict

(x : A) ≤ CDt

(x) + c.

Comments. Item

(a) and the next three exercises are from [P. Orponen, K. Ko, U. Sch¨oning, and O. Watanabe, J. Assoc. Comp. Mach., 41(1994), 96–121]. Item

(b) was suggested by L. Fortnow.