OpenAI and Anthropic Claim ETH Refutations as Lean Verification Sparks Community Review

Computer science spent two decades treating the Exponential Time Hypothesis as a convenient hardness anchor. ETH does not claim that P equals NP; it asserts something narrower and still brutal: solving 3-SAT on n variables should require time 2 raised to a linear fraction of n in the worst case. Hundreds of papers used ETH and its relatives— SETH, Gap-ETH, #ETH— to argue that scheduling, graph problems, and counting tasks cannot be sped up without breaking a shared barrier. On October 26, OpenAI said an internal model had refuted ETH, and hours later Anthropic published a parallel claim. The news is less about chatbots writing essays and more about whether a foundational conjecture survived contact with automated theorem discovery.

OpenAI’s preprint describes a deterministic algorithm that exactly counts satisfying assignments for fixed-width k-CNF formulas in subexponential time. For each fixed k, runtime is polynomial in n and m multiplied by 2 raised to roughly n divided by the square root of log n, with polylog factors. Because counting includes detecting zero assignments, the algorithm decides satisfiability as well. If the bound holds as stated, ETH and its counting cousin #ETH cannot both be true. OpenAI also released Lean formalization and said Impagliazzo, Paturi, and Williams— the researchers who shaped ETH— would organize an independent examination. Their open letter warned explicitly that participation is not certification.

Anthropic’s release followed the same arc with different timestamps and tooling. Its paper credits an internal Claude model with finding the core idea after enormous token output, emphasizes that the result does not settle P versus NP, and warns that practical speedups may require formulas with astronomically many variables before beating brute force. Anthropic’s Lean project reportedly covers a stronger statement than OpenAI’s Lean artifact, which analysts note aligns with a weaker exponent than the manuscript headline suggests. Independent bloggers who diffed the repositories found differences in comparator kernels, axiom usage, and whether “ETH is false” appears as a named theorem versus a corollary left to human interpretation.

The verification story is therefore split into three layers: the natural-language proof, the Lean proof of specific formal statements, and community acceptance that the formal statements match the conjecture researchers care about. Lean can verify implication structure without resolving whether definitions capture “worst-case 3-SAT time.” Anthropic’s paper admits that mapping English intent to formal definitions is not machine-checkable in the philosophical sense; OpenAI’s materials similarly caution that turning asymptotic bounds into production SAT solvers remains open work.

For working programmers, the immediate impact is near zero. SAT solvers in industry already exploit structure, parallelism, and heuristics that ignore worst-case ETH bounds. A subexponential worst-case algorithm with huge hidden constants does not automatically beat CryptoMiniSat on circuit verification instances. Anthropic’s own threshold— formulas larger than 10 to the 10,000 variables before beating exhaustive search in their bound— underscores the gap between asymptotics and benchmarks.

For complexity theorists, the impact could be enormous if the proof stands. Many conditional lower bounds would need revisiting, not because everyday problems become easy, but because the logical scaffolding tying them to SAT tightness would crack. Graduate courses would rewrite lectures on fine-grained complexity. Funding agencies might shift toward understanding which reductions preserve the new parameter regimes OpenAI and Anthropic exploit— groupings of variables, clause width fixes, and space bounds matter in the manuscripts.

The dual release also raises governance questions about competitive disclosure in mathematics. Two labs dropping ETH refutations within hours invites suspicions of parallel discovery or leaked hints, though both groups describe independent internal searches. The community’s healthy skepticism— amplified by detailed third-party posts comparing Lean statements— is exactly how mathematics should absorb AI-assisted claims. Speed of publication is now limited by social proof, not arXiv latency.

Security and cryptography researchers should not panic yet. ETH underpins some hardness arguments in cryptography, but modern cryptographic assumptions typically rely on stronger algebraic or lattice problems, not ETH alone. If ETH falls, papers that only assumed ETH for reductions to SAT might weaken, yet RSA, elliptic curves, and post-quantum schemes do not topple overnight. Still, review committees for standards bodies may ask whether any NIST documents cite ETH-dependent reductions— a niche audit worth doing.

Engineering leaders should treat vendor blog posts as starting points, not release notes for your dependency tree. Do not refactor NP-hard scheduling code because a headline said ETH died. Do watch hiring: formal methods, proof assistants, and complexity expertise are now strategic for AI labs validating model-generated mathematics.

Educational institutions face a curriculum puzzle. Teaching ETH as “likely true” is still reasonable this month, paired with a live case study in verification literacy. Students should read both preprints, both Lean repos, and Ryan Williams’ thread on organized review. That assignment teaches critical reading better than any static textbook problem set.

If the refutation holds, the deeper story is methodological: search in proof space may discover algorithms humans missed because human intuition anchored on ETH for twenty years. That does not mean models replace mathematicians; it means discovery pipelines now include generate-check loops at scale. Journals and conferences will need policies for AI co-authorship, data release, and reproducibility of million-token searches.

If the refutation fails, the story is still methodological: enormous claims can be formalized faster than communities can validate, creating a window where misinformation spreads on social media faster than referee reports. Either outcome pushes the field toward better tooling for statement alignment checks between prose and Lean.

Stackademic readers building SAT-related tooling should monitor the organized review’s outputs and avoid marketing “ETH-proof solvers” until constants are published and independently replicated. Meanwhile, celebrate that automated reasoning forced a public, transparent debate about one of complexity theory’s load-bearing walls— a debate that would have taken months to start without AI-assisted drafts and machine-checked cores.

The next milestones to watch: a unified errata from the review organizers, independent reimplementations of the counting algorithm on small k, and whether any STOC or FOCS committee fast-tracks a human-verified exposition. Until then, ETH belongs in the same bucket as any shocking preprint: fascinating, unfinished, and dangerous to cite in production SLAs.

Open-source maintainers of proof assistants should expect a spike in issues from newcomers trying to replay the Lean repos on laptops with insufficient RAM. Document hardware requirements and provide CI caches so curiosity does not turn into frustration.

Venture investors pitching “complexity-breaking startups” should be asked which instance classes they beat and with what constants. Asymptotic refutations rarely translate to SaaS margins without a narrow vertical where instance structure matches the theorem’s assumptions.

University hiring committees might weigh formal methods skills as highly as GPU cluster access when recruiting AI faculty this cycle. The ETH episode proves that verification pipelines are now part of frontier model releases, not an optional appendix.

If you maintain a technical blog, link primary sources— GitHub commits with timestamps, arXiv IDs, and the organizers’ letter— rather than screenshot threads. Future readers will judge this week by primary artifacts, not hype velocity.

Teaching assistants can run a classroom exercise: students pick one Lean definition from each lab and write in plain English what would need to be true for ETH to be false in the sense Impagliazzo and Paturi intended. Misalignment between English and Lean becomes visible quickly, which is the meta-skill ETH news accidentally teaches better than any textbook chapter on SAT.