4 ms·
By this justification exponentials wouldn't be any more interesting than stuff between exponentials and polynomials either, right? So why we still generally tau
by mehrdadn 7y ago
By this justification exponentials wouldn't be any more interesting than stuff between exponentials and polynomials either, right? So why we still generally taught both, but only these two? Aren't there an infinite number of complexities above polynomial to worry about? is my point.
- repsilat 7y ago"Exponential" is often colloquial short-hand for EXPTIME, which is closed under some useful operations (because there's an "any polynomial" in the exponent.) For one thing, it's robust to reasonable changes of model, for "No true Scotsman" definitions of "reasonable".
- mehrdadn 7y agoYou're talking about closure of EXPTIME under polynomial transformations. You could do similar for quasipolynomial and such; there's nothing about EXPTIME that makes it special in this regard. Edited my comment slightly to hopefully clarify.
- jules 7y agoExponential is interesting for P=?NP because the naive method for NP problems runs in exponential time.