[18]

(a) Let l(x) = n. Show that probabilities mt

(x)=2−Kt(x)

for the set of all x’s with Kt

(x) = O(log n) can be computed in time polynomial in t(n).

(b) Use Item

(a) to show that one can precompute mt

(x) with x ∈ A for the set A of high-probability x’s (Kt

(x) = O(log n)) in polynomial time for t(n) polynomial.

Comments. Source: [M. Li and P.M.B. Vit´anyi, SIAM J. Comput., 20:5

(1991), 911–935].