| ▲ | eli_gottlieb 4 hours ago | |
~~Yeah, that's NP-complete problems.~~ EDIT: DISREGARD THAT I WAS MISTAKEN | ||
| ▲ | csheehan10 4 hours ago | parent | next [-] | |
It's NP-complete problems if "subexponential" means O(2^{n^{\epsilon}}) for every \epsilon>0. If subexponential just means 2^{o(n)}, (as it is here, O(2^{n/\sqrt{\log n}})), then no. E.g. if the cost of the reduction took you from n to \sqrt{\log n}n, then you'd be back to exponential time. The Subexponential Reduction Family is the class of problems that preserve subexponential time in the second sense. | ||
| ▲ | LPisGood 4 hours ago | parent | prev [-] | |
That is unfortunately not the case | ||