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,

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.