[O46] We resume the discussion in Example 7.1.1.

(a) Is there an efficient invariance theorem for prefix Kolmogorov complexity based on the partial computable prefix function definition, Definition 3.1.2 on page 204? Efficiency here means simulation of a machine in the enumeration of the partial computable prefix functions by an optimal machine in, say, O(tlog t) steps for t steps.

(b) Is there an efficient universal partially computable function?

(c) Are the two notions of prefix Kolmogorov complexity efficiently equivalent?

Comments. Source: [D.W. Juedes and J.H. Lutz, Theor. Comput. Systems, 33(2000), 111–123].