The hypothesis that the difference between n and 2^n is not significant trivializes computational complexity theory.
-
-
Replying to @ModelOfTheory
What about the difference between 2^n and n^n?
1 reply 0 retweets 0 likes -
Replying to @noop_noob
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.
1 reply 0 retweets 1 like -
Replying to @ModelOfTheory @noop_noob
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).
1 reply 0 retweets 1 like -
Replying to @ModelOfTheory
OK. What about O(1) vs O(inverse ackermann(n)) vs O(n)?
1 reply 0 retweets 0 likes -
Replying to @noop_noob
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.
1 reply 0 retweets 1 like
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.
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.