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

Because polynomial complexity is the measure of what makes a tractable problem [1]. If the question is why - there's no formal reason. Tractability is really just subjective human standards: even high-degree polynomial time is often considered to not enough for a solution to be worthwhile computing.

[1][https://en.wikipedia.org/wiki/Cobham%27s_thesis]



Yes, my question was indeed why. At the very least, I would hope for explicit mentions that this is an arbitrary choice when the subject is being taught, and mentions of algorithms with running times between polynomials and exponentials. Otherwise it gives people the wrong impression that there isn't anything in between worth considering, which is misleading and just wrong.




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: