Hacker News new | past | comments | ask | show | jobs | submit login

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.



"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".


You'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.


Exponential is interesting for P=?NP because the naive method for NP problems runs in exponential time.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: