[29] Call polynomial-time computable if for some polynomial p and Turing machine T , the machine T on input n outputs 1:n in time

[29] Call χ polynomial-time computable if for some polynomial p and Turing machine T , the machine T on input n outputs χ1:n in time p(n). Prove that χ is polynomial-time computable if and only if for some polynomial p and constant c for all n we have Cp(χ1:n; n) ≤

c, where C(·; ·) is the uniform complexity of Exercise 7.1.7.

Comments. This is a polynomial-time version of the results about computable infinite sequences in Exercise 2.3.4.

Source: [Ker-I Ko, Theoret.

Comput. Sci., 48(1986), 9–33].