Anthropic posts a Claude-authored paper on GitHub claiming to refute the Exponential Time Hypothesis

Tue, Oct 27 04:35 UTC+8Updated Sat, Oct 31 20:54 UTC+8

Anthropic posted a paper on GitHub authored by Claude, "A 2^o(n) Time Algorithm for 3-SAT", which refutes the Exponential Time Hypothesis (ETH) and comes with a Lean 4 formalization. It says the core algorithm was found by an internal Claude research model with 14M output tokens and no human input. The same day, OpenAI posted a paper on GitHub saying ETH is false.

Why it matters

Anthropic posted a paper on GitHub authored solely by Claude, claiming a 2^o(n)-time algorithm for 3-SAT, which would refute the Exponential Time Hypothesis; the claim awaits peer verification.

Sources3

GitHub · anthropics/formal-mathGitHubTue, Oct 27 11:07 UTC+8A 2^o(n) Time Algorithm for 3-SATView original · Tue, Oct 27 11:07 UTC+8
GitHub · openai/mathGitHubTue, Oct 27 04:35 UTC+8The Exponential Time Hypothesis is FalseView original · Tue, Oct 27 04:35 UTC+8
@doteyXTue, Oct 27 13:30 UTC+8On the same day OpenAI announced that AI had refuted the "Exponential Time Hypothesis" (ETH), Anthropic released a paper on GitHub reaching the same conclusion, with only one listed author: Claude. The paper says the core algorithm was found on October 16 by an internal research version of Claude, using 1400万 (14 million) output tokens, with no human input. OpenAI says its own model also on October 16... https://twitter.com/__alpoge__/status/2114930095009968506Translated from Chinese · View original · Tue, Oct 27 13:30 UTC+8

Written by dalao.ai: the title, summary and why it matters are our own words. The original reports are the record; their publishers keep authorship.