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

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: