Both companies said their models had produced proofs that would disprove the Exponential Time Hypothesis, a longstanding conjecture in computational complexity.
On October 26, OpenAI said an unnamed internal model had found an algorithm refuting the Exponential Time Hypothesis (ETH), which holds that 3-SAT cannot be solved in subexponential time. Anthropic published a similar claim hours later in “A 2^o(n) Time Algorithm for 3-SAT,” credited to Claude. Both companies say their models reached the core result on October 16 and formalized proofs in Lean, a system that checks logical steps. Anthropic reports its model used 14 million output tokens, with no human input to the discovery. The work also claims faster exact counting of satisfying assignments, with a bound of 2^O(n log log n/√log n). If independently confirmed, the result would unsettle assumptions used across complexity theory and hundreds of research papers; it does not establish practical speedups or resolve P versus NP. ETH’s original proposers and MIT’s Ryan Williams are helping organize scrutiny, but neither proof has been peer-reviewed, and researchers have yet to verify that the formal statements match the intended conjecture.