Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The class of polynomial time algorithms is closed for some things, that you often see in algorithms: - If you run two polynomial time algorithms in parallel, the result is a polynomial time algorithm again. - If one operation of a polynomial time algorithm, is calling another polynomial time algorithm, then the result runs in polynomial time again.


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: