What about the difference between 2^n and n^n?
-
-
-
2^n < n^n < 2^(2^n), and the hypothesis implies the difference between 2^n and 2^(2^n) is not significant by substitution, so the difference between 2^n and n^n is not significant either.
-
And the difference between 2^n and n^n isn't that significant in the real world either; both are prohibitively large, and the closure of TIME(2^n) under polynomial-time reductions contains TIME(n^n).
-
OK. What about O(1) vs O(inverse ackermann(n)) vs O(n)?
-
Assuming 1 ≈ n or 1≈ inverse ackermann(n) implies 1 ≈ f(n) for any f by substitution. This is what is typically assumed in recursion theory.
-
Assuming n ≈ inverse ackermann(n) implies n ≈ 2^n, hence trivializes complexity theory, and it also implies primitive recursive functions are tractable. It leaves open the possibility that whether Peano Arithmetic can prove a computable function is total is important, though.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.