The hypothesis that the difference between n and 2^n is not significant trivializes computational complexity 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.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
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.