points by LPisGood 3 days ago | 0 comments
> To be clear though, it does not imply that NP is subexponential
Is there a subset of NP problems for which a subexponential algorithm would witness the entire NP class being subexponential?
[–] eli_gottlieb 3 days ago
[–] csheehan10 3 days ago
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 3 days ago
That is unfortunately not the case
EDIT: DISREGARD THAT I WAS MISTAKEN