News for hackers. Stuff that matters.
Re:A New Map Traces the Limits of Computation by thomasahle on Wednesday September 30, 2015 @08:02AM (#10303265)
Basically:

- If you can solve k-sat in time (2-eps)^n, you've refuted SETH.

- If you can solve 3-sat in time (1+o(1))^n, you've refuted ETH.

- If you can solve 3-sat in time n^O(1), you've refuted P!=NP.

Since general k-sat is at least as hard as 3-sat, it follows that SETH is the strongest hypothesis (hence the name) and thus the most likely to fall. P!=NP is the weakest hypothesis and thus the most likely of the three to be true.

Re:A New Map Traces the Limits of Computation by darkmighty on Wednesday September 30, 2015 @11:38AM (#10304723)
is (1+o(1)) essentially anything subexponential but hyperpolynomial?
Re:A New Map Traces the Limits of Computation by thomasahle on Wednesday September 30, 2015 @02:08PM (#10305879)
Yeah anything subexponential. We can also write it as `2^o(n)`.

It doesn't have to by hyperpolynomial, if you solve ETH in linear time, you also refute it :-)