News for hackers. Stuff that matters.
Re:The Exponential Time Hypothesis Is False [pdf] by eli_gottlieb on Monday October 26, 2026 @11:08PM (#50254294)
Yeah, that's NP-complete problems.
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.

Re:The Exponential Time Hypothesis Is False [pdf] by LPisGood on Monday October 26, 2026 @11:29PM (#50254410)
That is unfortunately not the case