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

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.


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: