Conjecture on the impossibility of universally ultra-tight oracle-use bounds

Let XX and YY be infinite binary sequences, and let an oracle computation of XX by YY have an oracle-use function measuring how many bits of YY are queried to compute the first nn bits of XX. Write XnX\upharpoonright_n for the length-nn prefix of XX, and let K(Xn)K(X\upharpoonright_n) denote its prefix-free Kolmogorov complexity. Oracle-use conjecture. There exists XX such that, for every YY computing XX, the oracle-use in the computation is not bounded above by the function nK(Xn)n\mapsto K(X\upharpoonright_n). This asserts that the stronger bound suggested by the general upper bound K(Xn)+lognK(X\upharpoonright_n)+\log n is not achievable for every sequence. Bounds of this form are connected with online coding methods and the complexity of initial segments; the cited special case of left-c.e. reals shows that a related bound can be achieved in some cases, while the general impossibility claim is presented here as a conjecture.

Sources & referencesView supporting material

Primary source

George Barmpalias and Andrew Lewis-Pye, “Compression of data streams down to their information content”, arXiv:1710.02092 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.