The right upper bound conjecture for automatic complexity structure functions

About 12 years old · traced to

Let hx(m)h_x(m) be the minimum number of states of a nondeterministic finite automaton accepting xx and at most bmb^m strings of length ∣x∣\lvert x\rvert, let gx(m)=hx(∣x∣−m)g_x(m)=h_x(\lvert x\rvert-m), and let Gn(m)=sup⁡∣x∣=ngx(m)G_n(m)=\sup_{\lvert x\rvert=n}g_x(m). The right upper bound conjecture. For every fixed integer kk,

lim⁡n→∞Gn(k)=k+1.\lim_{n\to\infty}G_n(k)=k+1.

This conjecture predicts the asymptotic maximum of the converse structure function at each fixed parameter kk; the supplied text gives no evidence that it has been resolved.

References

Primary source

Bjørn Kjos-Hanssen, “Kolmogorov structure functions for automatic complexity”, arXiv:1409.0584 (2020).

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.