The Exponential Time Hypothesis Is False [pdf]

Commenters described the claimed result as a deterministic, formally verified algorithm for exactly counting satisfying assignments of k-CNF formulas in subexponential time, challenging the Exponential Time Hypothesis and related assumptions. They stressed that this does not show P = NP or make all NP problems subexponential: polynomial-time reductions can expand an input into many more SAT variables, wiping out the speedup. The advantage may transfer to problems reducible to SAT with only a linear increase in variables, with counting independent sets and colorings offered as examples. Some commenters saw the result as a major blow to complexity assumptions used in prior work; others cautioned that refuting SETH does not by itself yield faster self-attention, since the implication cannot simply be reversed.

Views also divided over significance and credibility. A SAT-solving expert called the algorithm “galactic,” with no immediate practical applications, while noting that its ideas might inspire useful techniques; another commenter emphasized that real-world SAT instances can behave better than worst-case bounds suggest. Some celebrated the result as extraordinary, while skeptics objected that part of the construction relies on an enormous precomputed lookup table and questioned whether the formal system’s assumptions capture meaningful computation. Others countered that the paper specifies a real algorithm with a proved bound, even if it is far too slow to matter for practical SAT or cryptography.