The right upper bound conjecture for automatic complexity structure functions

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(xm)g_x(m)=h_x(\lvert x\rvert-m), and let Gn(m)=supx=ngx(m)G_n(m)=\sup_{\lvert x\rvert=n}g_x(m). The right upper bound conjecture. For every fixed integer kk,

limnGn(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.

Sources & referencesView supporting material

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.