The right upper bound conjecture for automatic complexity structure functions
The right upper bound conjecture for automatic complexity structure functions
Let be the minimum number of states of a nondeterministic finite automaton accepting and at most strings of length , let , and let . The right upper bound conjecture. For every fixed integer ,
This conjecture predicts the asymptotic maximum of the converse structure function at each fixed parameter ; 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
Sign in to submit a solution.
No solutions have been posted yet.