Conjecture on the impossibility of universally ultra-tight oracle-use bounds
Conjecture on the impossibility of universally ultra-tight oracle-use bounds
Let and be infinite binary sequences, and let an oracle computation of by have an oracle-use function measuring how many bits of are queried to compute the first bits of . Write for the length- prefix of , and let denote its prefix-free Kolmogorov complexity. Oracle-use conjecture. There exists such that, for every computing , the oracle-use in the computation is not bounded above by the function . This asserts that the stronger bound suggested by the general upper bound 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.