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

Polynomials are convenient because they allow you to mostly ignore the details of the underlying model of computation. E.g. if you try to simulate a multi-headed Turing machine with a single-headed one, you'll spend a lot of time moving between different positions on the tape, increasing the runtime complexity by a polynomial factor. By considering all polynomials as essentially equivalent, you can choose whichever abstraction you want without having to think too hard about the overhead it adds. That's of course bad if you actually want to implement the fastest algorithm, but it makes proving (and stating) theorems a lot simpler.


Yup this is the justification for why polynomial reductions should define everything within class, but it doesn't seem to justify why we should only focus on the polynomial and exponential classes to begin with, given there are infinitely many classes in between (and beyond exponential). Sorry my question didn't make it clear that's what I was asking about; I edited it to hopefully clarify.


Complexity theorists do care about reductions within subexponential time classes, but it's not a great topic for P vs NP focused Complexity Theory 101. And when you do focus on P vs NP, the dichotomy is quite natural because of the https://en.wikipedia.org/wiki/Exponential_time_hypothesis, the conjecture that a broad class of NP-complete problems are 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: