[30] Let f(n) be computable in polynomial time and satisfy the condition 2f(n) = . Then for every infinite sequence , there is a polynomial

[30] Let f(n) be computable in polynomial time and satisfy the condition 2−f(n) = ∞. Then for every infinite sequence ω, there is a polynomial p such that for infinitely many n, we have Cp(ω1:n|n) ≤

n − f(n).

Comments. This is a polynomial-time version of Theorem 2.5.1 on page 143. Source: [Ker-I Ko, Ibid.].