[39] Use the definition of ic in Exercise 7.4.7.

(a) Show that if ic(x : A) ≤ log C(x)−1 for all but finitely many x, then A is computable.

(b) There is an incomputable computably enumerable set A and a constant c such that ic(x : A) ≤ log C(x) + c for all but finitely many x.

Comments. Item

(b) resolves an open question in the first edition of this book: it refutes the unbounded version of the instance complexity conjecture in Example 7.4.1.

Originally proposed by P. Orponen, K. Ko, U. Sch¨oning, and O. Watanabe [Ibid.]. The solution is due to M. Kummer

[Ibid.], where Item

(a) is attributed to J.T. Tromp.