Conjecture on the impossibility of universally ultra-tight oracle-use bounds
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.