A 2^o(n) time algorithm for 3-SAT
github.com
2 threads
This isn't getting any attention, but Anthropic claims Claude independently proved that the Exponential Time Hypothesis was false back on October 16th, and had been working on a cleaned-up draft.
It's a bit sus that the time complexity and also the fact it solves the counting version of the problem, match exactly the openAI result
It is weird. We'll have to wait and see if they are the same algorithm or not.
Is it 2^O(n) or 2^o(n)? (Edit: It's the latter according to the site, HN possibly mangled the title.)