[27] Similar to Definition 7.5.1, one can define the Ct version of Kt. Below we set n = l(x).

(a) Show that Ct(x) ≤ s(n) implies x ∈ C[s(n), 2s(n), ∞], and the last formula implies Ct(x) ≤ 2s(n).

(b) For a CFL L, let CL(n) = min{Ct(x) : x ∈ L=n}. Show that CL(n) =

O(log n).

(c) Define CL(n) = max{Ct(x) : x ∈ L=n}. Show that L is P-printable iff L is in P and CL(n) = O(log n).

(d) Show that CL(n) = O(log n) for all L in P iff CL(n) = O(log n) for all L in NP.

(e) Every nondeterministic exponential-time computable predicate L is computable in deterministic exponential time iff CL(n) = O(log n).
Comments. Source: [E. Allender, in: Kolmogorov Complexity and Computational Complexity, O. Watanabe, ed., Springer-Verlag, 1992, pp. 4–
22]. This reference contains applications of CL(n) and CL(n) in random oracle constructions, pseudorandom generators, and circuit complexity.