Discussion about this post

User's avatar
Raina Vichitra's avatar

> I’m not a betting man

We have all read the sports forecasting blogs Ben

Paul Beame's avatar

From the beginning, ETH and SETH were "straw man" hypotheses, not conjectures. They were set up for two reasons (1) as challenges to anyone conjecturing P=NP: Why haven't you refuted this yet? and (2) as ways of exploring what the relationships between problems would be like if the true complexity of SAT is at a scale way larger than polynomial. (There was lots of work getting constant-factor improvements in the exponent on brute force problems, but it had been unclear how they were related.)

Lots of things that papers claimed as consequences of SETH actually showed them to be consequences of OV, a much weaker hypothesis than SETH (and apparently not refuted by the refutation of ETH) that didn't have the cachet of talking about SAT, so some of the loss has been a matter that the "sales pitch" for papers rather than their core content. More generally, it was always the case that many of these results were really of the form: "You may have thought that SAT was too abstract or impractical compared to the problems you were working on but, in fact, any ideas you come up with automatically apply to SAT."

There is a very large gap between the latest very small improvement in exponent and P=NP. There are many natural milestones between ETH and P=NP: Beat 2^{n^{1-o(1)}}, beat 2^{n^{c}} for fixed c<1, (e.g. c ~ 1/3 for integer factoring algorithms), get 2^{n^{o(1)}}, etc. There is no reason to expect that a galactic-exponent polynomial-time algorithm for SAT is more likely than any of these others and there are lots of other weaker forms analogous to ETH that now stand as a series of challenges to anyone who thinks that galactic-exponent polynomial time is likely. Do you have particular reason to believe that none of these other scales is right?

The situation with the galactic constants in the new algorithms is worse but similar in kind to those for matrix multiplication algorithms for years - this isn't some new phenomenon just because it's AI.

However, because of the scaling in some of the reductions, the fact that these only are relevant for galactic sizes doesn't actually mean that they have no real impact at more reasonable sizes for previous claims about problems we care about. Unfortunately, some of the details of the reductions based on ETH scale up any savings in a drastic way (e.g. the most well-known reduction that would give f(k) n^{\Omega(k)} for k-clique assuming ETH ends up losing something close to a k^{1/3} in its exponent if the current SAT bounds were optimal.)

16 more comments...

Ready for more?