NewsLab
Oct 27 19:41 UTC

A 2^O(n) Time Algorithm for 3-SAT (github.com)

4 points|by nryoo||4 comments|Read full story on github.com

Comments (4)

4 shown
  1. 1. QuesnayJr||context
    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.
  2. 2. dooglius||context
    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
  3. 3. QuesnayJr||context
    It is weird. We'll have to wait and see if they are the same algorithm or not.
  4. 4. commandersaki||context
    Is it 2^O(n) or 2^o(n)? (Edit: It's the latter according to the site, HN possibly mangled the title.)