[42] If one does not care about decompression time then there exist fast and almost optimal probabilistic algorithms for compression.

Let x be a string of length n.

(a) Show that for each Turing machine U, for each computable time bound

f, each algorithm that for all x maps (x, C(x)) to a program for x of length C(x) +o(n), must have a running time that exceeds f(n) for some x of length n.

(b) Let U be a standard Turing machine as defined in Exercise 7.3.15.

use U as reference Turing machine. Show that there exists a probabilistic algorithm that on input  > 0, k and x outputs a program of length k + O(log(n/)) for U such that if k ≥ C(x) this program outputs x.

Moreover, the algorithm uses 2O(n) space and O(log(n/)) random bits.

(c) Show that there exists a probabilistic polynomial time algorithm that on input  > 0, k and x outputs a program of length k + O(log3(n/))

such that if k ≥ C(x) this program outputs x. The algorithm uses O(log3(n/)) random bits.

Comments. Source: B. Bauwens’ email of August 17, 2017. Item

(a) is easiest. It shows that while no computable function can generate shortest programs of all strings (otherwise we could compute the Kolmogorov complexity), given a string together with its Kolmogorov complexity computing a shortest program requires more than computable time. Hint for Item (b): First, show the claim for the case k = C(x). Let D be the degree of a left node in the extractor and [D] = {1, 2,...,D}. Obtain programs for x using extractors and logarithmic hash codes. Show that a (k, ε)-extractor function f : {0, 1}n × [D] → {0, 1}k has the following property: For every S ⊆ {0, 1}n there are at most 2k elements x such that more than a 2ε-fraction of i ∈ [D] satisfy d(f −1(f(x, i))  S) >

d(S)D/(εM). Note that a random function with D = O(n) is an extractor. The programs for x are obtained from values of f(x, i) for a random i ∈ [D] together with a hash code of logarithmic bit length. Hint for Item

(c): use the extractor from [R. Raz, O. Reingold and S. Vadhan, Proc.

30th ACM Symp. Theory Comput., 1999, 149–158] Theorem 1 Item (2).

This extractor has a prefix property. Note that for all k ≤ n, by taking k-bit prefixes of the function

f, we obtain (k, ε)-extractors.