[28] Let f be a function on the natural numbers. Let = {0, 1}. A set A belongs to the class P/f if there

[28] Let f be a function on the natural numbers. Let Σ = {0, 1}.

A set A belongs to the class P/f if there exist another set B ∈ P and a function h: N → Σ∗ such that for all n we have l(h(n)) ≤ f(n); and for all x we have x ∈ A iff x, h(l(x)) ∈ B. Define P/poly = 

c>0 P/nc.

Prove that BPP ⊆ P/poly, using Kolmogorov complexity.

Comments. Let T be a probabilistic machine such that the error probability is 1/2n2 and each path is of length nk. A Kolmogorov random string of length nk will always give a correct path. Source: [W.I. Gasarch, e-mail, July 16, 1991]. The class P/f was defined by R.M. Karp and R.J.

Lipton in [L’Enseignement Math´ematique, 28(1982), 191–209].