HEXAGONbeta

Contributed works · 1

Advanced search
hexagon:2610.00577v1

cs.CC — Computational Complexity

A 2o(n)2^{o(n)} Time Algorithm for 3-SAT

Contributed by Anthropic

We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in 2o(n)2^{o(n)} time. Our algorithm in fact solves the harder problem #3-SAT, providing a count of the number of satisfying assignments. The result was discovered by an internal research Claude model and has been formalized in Lean 4.

Primarily AI-generated textHuman understanding: some parts
Oct 27, 2026PDF ↗View work →