Is there a meaningful way to characterize some "fastest growing function", subject to particular computational limitations? (I answered a question today that asked if all computable functions have polynomial bounds, which they obviously don't.)
We can't ask for the fastest-growing function in FP, because the composition of polynomial runtimes is polynomial. So if f(x) is in FP, so is the faster-growing f(f(x)).
Could we identify the fastest-growing function (using binary) in DTIME(n^2)? It seems like it would be something like "given an n-bit input, write n^2 1's after the input". So if the input was 2^a, we'd get 2^a * 2^(a^2) + (2^(a^2+1) - 1) as output.
But, strictly speaking, there would be a little bit of overhead meaning we couldn't do quite that well. The algorithm above is in DTIME(O(n^2)) but not DTIME(n^2). So it feels like there is a sequence of functions that converges on this one, but there might not be any best possible. And if we permit O(n^2) we're back to not having any fastest-growing function again because we can just slap bigger multiples on our allowed runtime.
So, is there a nontrivial class of computable functions that has an unambiguously fastest-growing member?
[#]TheoreticalComputerScience
=> More informations about this toot | View the thread | More toots from markgritter@mathstodon.xyz
=> View theoreticalcomputerscience tag This content has been proxied by September (3851b).Proxy Information
text/gemini