OpenAI Claims Algorithm That Would Refute the Exponential Time Hypothesis, Pending Expert Review

OpenAI claims a deterministic algorithm that exactly counts satisfying assignments of fixed-width CNF formulas in subexponential time and polynomial space. Its 3-SAT case would refute the Exponential Time Hypothesis. An independent working group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will examine the proof; the claim is under expert review, not accepted. Announced October 26, 2026.