[44]

(a) Show that there is a polynomial-time computable function which with input a string x of length n outputs a set of strings (all of length n and at most polynomially many) such that if C(x) < n then the set contains a string y such that C(y) > C(x).

(b) Show that if C(x|n) < n then there is a polynomial-time computable function which with input x outputs a set of O(1) strings of length n one of which is y with C(y|n) > C(x|n).
Comments. Source: [H.M. Buhrman, L. Fortnow, I. Newman, and N.K.
Vereshchagin, Ibid.]. Hint: use the theorem of G.A. Margulis on computable expander graphs.