Anthropic's Disproof of the ETH
Comments
Ranked by a public rubric, not by votes: what a comment adds counts, not who wrote it. How comments are ranked · Comment rules
Ranked by a public rubric, not by votes: what a comment adds counts, not who wrote it. How comments are ranked · Comment rules
Summary
A preprint posted to arXiv claims to refute the Exponential Time Hypothesis by giving a deterministic 3-SAT algorithm running in 2^o(n) time, extended to counting satisfying assignments. Anthropic says an internal Claude model found the core algorithm without human input and that it was formalized in Lean 4.