3 ms·
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 t
by mehrdadn 7y ago
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.
- skinner_ 7y agoComplexity 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 https://en.wikipedia.org/wiki/Exponential_time_hypothesis, the conjecture that a broad class of NP-complete problems are exponential-time.