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

I think the answer is much more trivial than you think. Polynomials and exponential complexities are given such special status simply because when we start classifying "natural" problems, many of them either fall into one of these classes, and not many in the intermediate classes. If they fell into polynomial and sub-exponential time, computer science text books would have chapters dedicated to these two instead. At the end of the day CS is used to make building technology easier and so computer scientists naturally interested in "natural" problems and not artificially designed problems.

Now, why "natural" problems so easily fall into these two categories and not others is a different mystery and not what you asked.




It's also a robust distinction because polymomials are closed under addition, multiplication and composition.

Converting an algorithm from a Turing machine to a random-access model will often give you a polynomial speedup, but not an exponential one, so "polynomial time" means the same for both.

If you have a problem A, and a polynomial reduction from A to B, and a polynomial algorithm for B, you have a polynomial algorithm for A.

Sometimes algorithms can be polynomial but intractable (or even exponential but practical for some real cases), but it's less "neat" or clean to reason about those things. (Very useful, though, just more done outside the academy.)

As for things that aren't polynomial, I guess exponential things just happen to be the most common kind? Not sure myself why "pseudo-polynomial" bounds aren't more common.




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: