Claimed AI-led

A subexponential counting algorithm for fixed-width CNF, refuting the Exponential Time Hypothesis

A 67-page preprint authored by OpenAI gives a deterministic algorithm that exactly counts the satisfying assignments of a $k$ -CNF formula in subexponential time and polynomial space, refuting the Exponential Time Hypothesis in the case of 3-SAT; OpenAI released it with a Lean formalization of a weaker bound than the manuscript claims, and announced that an independent working group of complexity theorists would examine the proof.

Lab: OpenAI
Model: Unreleased internal OpenAI model, not named in the release
Field: Computer science
Date: 2026-10-26
Problem posed: 1999 · open 27 yrs

Sources

What was found

For every fixed $k \ge 2$ the preprint gives a deterministic algorithm that computes the exact number of satisfying assignments of a $k$ -CNF on $n$ variables and $m$ clauses in $\mathrm{poly}_k(n, m)$ space and time $(n+m)^{O_k(1)} 2^{n/(\log n)^{1/2+o(1)}}$ . Since testing whether that count exceeds zero decides satisfiability, the case $k = 3$ contradicts the Exponential Time Hypothesis. The manuscript is dated 17 October 2026 and revised 25 October 2026, and its stated techniques are exact counting, sparse parity tests and polynomial interpolation. It was published on 26 October 2026 into openai/math, the repository of 721 manuscripts in 373 families that this registry already records at 2026-10-06-openai-math-collection, whose README frames the manuscripts as raw research data rather than polished papers and reports roughly 42 percent of top-line results formalized. The release note says an independent working group of computer scientists led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will examine and explain the proof, and that OpenAI made the materials public immediately at the group's request.

Novelty check

Searched arXiv on 2026-10-27. The hypothesis was standing rather than previously refuted: abs:"exponential time hypothesis" AND abs:"refute" returned 18 records, all of which assume ETH to derive lower bounds rather than attacking it; ti:"exponential time hypothesis" returned 6 and abs:"3-SAT" AND abs:"subexponential" returned 7, none claiming a subexponential 3-SAT algorithm. Within this registry the preprint is one manuscript from the openai/math collection recorded at 2026-10-06-openai-math-collection, which covered the release as a whole and predates this result; this entry exists because an ETH refutation is a specific claim with its own artifacts and its own review, not because the collection entry missed it. The other ETH refutation of the same day is recorded at 2026-10-26-eth-refuted-claude, and Anthropic's paper cites this one as independent and concurrent. The two bounds are close but not identical, this one being $(n+m)^{O_k(1)} 2^{n/(\log n)^{1/2+o(1)}}$ against Anthropic's $2^{O(\min\{km/\sqrt{\log m},\ k^2 n \log\log n/\sqrt{\log n}\})}$ , so reports that the two labs reached the same bound are approximate.

Caveats and known objections

Entered at claimed. A Lean formalization does exist, which distinguishes this from an unformalized manuscript, but three things keep the grade below formal. First, the formalized statement is weaker than the published one: OpenAI's own scope page records that Lean proves a time bound of $(L+1)^{O_k(1)} 2^{O_k(n (\log\log n)^2/\sqrt{\log n})}$ on a canonically encoded formula of bit length $L$ , while the manuscript claims the sharper $(n+m)^{O_k(1)} 2^{O_k(n \log\log n/\sqrt{\log n})}$ . The weaker bound is still subexponential and so still refutes ETH, but it is not what the paper's abstract states. Second, the Comparator configuration for this result sets enable_nanoda to false, so unlike the concurrent Anthropic development it is not re-checked by a second independent kernel. Third, no external checker has examined it: the MathVet review of openai/math that this registry already cites covers four other SAT-related results from the October release and has no row for this one, and the build was not rerun for this entry. The grade is therefore a statement about what has been checked, not a judgement that this result is weaker than the concurrent one at 2026-10-26-eth-refuted-claude, which is graded formal because its axiom print and second-kernel check are documented. The reliability of the surrounding collection is part of the context: OpenAI withdrew three manuscripts from the same repository on 7 October 2026 over a sign error and revised 14 others, and its README says some unformalized results could have issues. The announced working group led by Impagliazzo, Paturi and Williams has published nothing, and OpenAI's note describes its role as examining and explaining rather than certifying. The only third-party material, the ProveIt collection cited here, states that nothing in it has been checked there and that its derivative reports assume the preprint's arguments unchanged; one of them notes the formalized bound is weaker than the manuscript's, agreeing with OpenAI's own scope page. The paper gives no practical algorithm and does not resolve P versus NP. Autonomy is graded ai-led on the strictest defensible reading, matching every other entry from this release: the repository README says the manuscripts came from an unreleased internal model given roughly three hours of thinking compute per result across about 4,000 posed problems, and records human editing for only one unrelated write-up, but the problems, the formalization pipeline and the release were human-run. No human author is named on the preprint.

No independent check is recorded on this entry yet.

Reading the primary source closely enough to say whether it supports the claim counts as a check, and you are credited on the entry.

Submit a check Challenge the grade

Or on GitHub: submit a check challenge the grade send a correction or send a pull request

Entry history (1 event)

2026-10-27AddedEntered the registry graded Claimed and AI-led.

Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.

Graded claimed for verification and ai-led for autonomy. What these mean.

Cite this entry

Plain text

whataifound.org. (2026). A subexponential counting algorithm for fixed-width CNF, refuting the Exponential Time Hypothesis. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-10-26-eth-refuted-openai

BibTeX

@misc{whataifound-openai-2026-openai,
  title        = {A subexponential counting algorithm for fixed-width CNF, refuting the Exponential Time Hypothesis},
  author       = {{whataifound.org}},
  year         = {2026},
  howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
  note         = {Result by OpenAI. Verification: Claimed. Autonomy: AI-led.},
  url          = {https://whataifound.org/finding/2026-10-26-eth-refuted-openai}
}

Related findings

Formally verifiedA subexponential algorithm for counting 3-SAT solutions, refuting the Exponential Time HypothesisAnthropic · 2026-10-26 Author verifiedTruly subquadratic 3SUM and truly subcubic APSP, refuting two central fine-grained complexity hypothesesAnthropic · 2026-10-05 Formally verifiedSix-task counterexample to the Kernel Conjecture of pinwheel schedulingIndependent · 2026-09-30

algorithms fine-grained-complexity sat counting lean formalization construction

← All computer science findings in the registry

A subexponential counting algorithm for fixed-width CNF, refuting the Exponential Time Hypothesis

Sources

Original work

Announcement

Independent commentary

What was found

Novelty check

Cite this entry

Related findings