News for hackers. Stuff that matters.
Re:The Exponential Time Hypothesis Is False [pdf] by csheehan10 on Monday October 26, 2026 @11:31PM (#50254420)
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.

There are no comments on this comment yet.