From my interpretation of reading the result by OpenAI, they also show this:
In this paper, we refute ETH by giving, for every fixed k >= 2, a deterministic algorithm that counts the satisfying assignments of a k-CNF in subexponential time and polynomial space.
Anthropic has now published a proof that #3SAT is also subexponential
score 2 · canonical
From my interpretation of reading the result by OpenAI, they also show this:
score 1 · canonical
Yup, they do, didn’t read the OpenAI paper clearly enough!
score 1 · canonical
Wow.
“The exponential time hypothesis is false — proof left as an exercise for the reader.”
score 1 · canonical
Ah yes, when the author channels their inner Fermat.
score 1 · canonical