[33] In Definition 7.4.1 on page 591, when we allow t to be an arbitrary finite time, we will remove t from ict and simply write ic.

(a) Let R = {x : C(x) ≥ l(x)}. We know that R is infinite and that it contains at least one string of each length. Show that there is a constant c such that for every x in R we have ic(x : R) ≥ C(x) −

c. That is, R contains only hard instances.

(b) Strings with high Kolmogorov complexity are individually hard to recognize by bounded computations. We say that a set C is dense if there is an  such that d(C  Σn) ≥ 2n. Let set A be complete for the class 

c≥0 DTIME[2cn] with respect to polynomial-time reductions.

Show that there is a dense subset C ⊆ A such that for every nondecreasing polynomial t(n) ≥ n log n, for each x ∈ C, ict

(x : A) ≥ Ct(x) − c, for some constant c.

(c) For every computably enumerable set A with an infinite complement, there exists a constant c such that for infinitely many x ∈ A we have ic(x : A) ≥ C(x) − c.

(d) Show that there is a computably enumerable set A with ic(x : A) ≥
l(x) for infinitely many x ∈ A.
Comments. Hint for Item (a): Let L(p) be the set of strings accepted by p in the ic sense. Observe that there is a constant d such that for every total p for which L(p) ⊆ R, and for every x ∈ L(p), we have l(x) ≤ l(p) +

d. (This is similar to Corollary 2.7.2 on page 179.) Now the result follows easily using the definition of ic. Item

(b) may be regarded as another special case of the instance complexity conjecture in Example 7.4.1.

Items (a)–

(c) are from [H.M. Buhrman and P. Orponen, J. Comput. System Sci., 53:2(1996), 261–266]. Item

(d) and an extensive study of related topics can be found in [M. Kummer, SIAM J. Comput., 25:6(1996), 1123–1143].