[43] (a) Show that there exists an algorithm that on input a string x of length n and a rational number > 0 outputs

[43]

(a) Show that there exists an algorithm that on input a string x of length n and a rational number δ > 0 outputs a list of strings of length n such that the size of the list is O(n2)p (with p a polynomial in 1/δ) satisfying the following property: if C(x) < n−log log n−O(1) then a (1 − δ)-fraction of the strings in the list have Kolmogorov complexity greater than C(x) where the constant hidden in the O(1) term depends on δ.

(b) Show that there exists an algorithm that on input a string x of length n and a rational number δ > 0 outputs a list of strings of length n such that the size of the list is O(n)p (with p a polynomial in 1/δ) and the following property holds: if C(x) < n−log n−O(1) then a (1−δ)-fraction of the strings in the list have Kolmogorov complexity greater than C(x)

where the constant hidden in the O(1) term depends on δ.

(c) Show that there exists an algorithm that on input a string x of length n and a rational number δ > 0 outputs a list of strings of length n such that the size of the list is 2O(log3 n) and the following property holds: if C(x) < n − O(log3 n) then a (1 − δ)-fraction of the strings in the list have Kolmogorov complexity greater than C(x) and the algorithm is polynomial time in the sense that on input x, i the ith string in the list is computed in polynomial time.

Comments. Source: [M. Zimand, Proc. 34th Symp. Theoret. Aspects Comput. Sci., Leibniz Int. Proc. Informatics (LIPIcs, Dagstuhl, Germany), 66(1017), 58:1–58:12 or arXiv: 1609.05984.v4 [cs.CC], 6 February 2017]. The three items are similar but each has a different advantage.

Consider strings x of length n. Item

(a) allows the string x to have the highest Kolmogorov complexity; Item

(b) aims at the shortest list;

Item

(c) computes the list in the shortest time (Items

(a) and

(b) have computable algorithms but Item

(c) has a polynomial-time computable algorithm). Hint: use a particular type of bipartite graph, an elaboration of the graphs used in Exercise 7.3.16.