Anthropic's Disproof of the ETH (hexagonmath.org)

Anthropic has made a significant breakthrough by presenting a deterministic algorithm for the 3-SAT problem running faster than the previously believed exponential time frame, specifically achieving a time complexity of 2^(o(n)). This algorithm not only addresses the satisfiability question but also extends its capabilities to the #3-SAT problem, enabling the counting of satisfying assignments. What is particularly noteworthy is that this algorithm was generated autonomously by an internal model called Claude, which demonstrated a remarkable capacity for algorithmic discovery without human intervention. This development challenges the long-held Exponential Time Hypothesis (ETH) and could have profound implications for the AI and machine learning community, particularly in fields reliant on combinatorial optimization and algorithm design. By formalizing the findings in Lean 4, a proof assistant, Anthropic is not only enhancing the rigor of their claims but also contributing to the broader discourse on computational complexity. Concurrent reports from an internal OpenAI model achieving similar results suggest a burgeoning exploration in this area, highlighting the potential for collaborative advancements in algorithmic research motivated by AI-driven insights.