Right, relaxing the "it must grow faster than polynomial" might free up some new methods that we've foregone. But it's also the case that existing methods migh

Right, relaxing the "it must grow faster than polynomial" might free up some new methods that we've foregone. But it's also the case that existing methods might still work fine - breaking them wouldn't be Omega(exp(n)), but may still have a high enough lower-bound for realistic values. Of course, if we discover that P=NP, getting at those lower bounds would be a priority...