[Dylan16807]

P versus NP could be a red herring too.

If P=NP, but the best asymptotic solution is n^7, and it has so much overhead that the best practical solution is n^9, then it doesn't really matter that it isn't exponential. It's still unsolvable for easily accessible problem sizes.

[lostmsu]

You think 7 and 9 are fun, imagine the number is instead astronomically big as in BB(8).