Exponential Time Hypothesis

The exponential time hypothesis (ETH) is a conjecture in computational complexity theory about how fast the 3-SAT problem can be solved. It says that deciding whether a Boolean formula in 3-CNF form on $n$ variables is satisfiable cannot be done in subexponential time: some constant $s > 0$ exists such that every algorithm for 3-SAT needs time of order $2^{sn}$ in the worst case.^[1][3] Russell Impagliazzo and Ramamohan Paturi stated the hypothesis in work published in 1999 and 2001, and a companion paper with Francis Zane supplied the sparsification lemma, the main tool for transferring the hypothesis to other problems.^[1][2][3] A stronger form, the strong exponential time hypothesis (SETH), says that the savings over brute-force search for $k$-SAT vanish as the clause width $k$ grows.^[3][4]

For more than two decades researchers used ETH and SETH as assumptions behind conditional lower bounds. Through them, the presumed hardness of satisfiability was turned into precise running-time limits for graph problems, parameterized problems and problems solvable in polynomial time.^[3][6] On 26 October 2026, OpenAI published a manuscript, written by an unnamed internal model, claiming a deterministic subexponential-time algorithm for 3-SAT that would refute ETH. Hours later, Anthropic released a separate paper credited to Claude making a similar claim.^{[16][18][20][28]} Both claims came with Lean formalizations. As of 28 October 2026, neither had been peer reviewed. A working group led by Impagliazzo, Paturi and Ryan Williams was organizing an open community examination, and the organizers said their involvement "should not be taken as certification of the claim."^[23]

Definition

k-SAT and the constants s_k

In the $k$-SAT problem the input is a Boolean formula in conjunctive normal form, an AND of clauses, where each clause is an OR of at most $k$ literals (variables or their negations). The question is whether some assignment of true and false values satisfies every clause. Trying all $2^n$ assignments solves the problem, and the formula can be checked against any single assignment quickly.^[20] 3-SAT is NP-complete, so a polynomial-time algorithm for it would show P = NP.^[20]

Following Impagliazzo and Paturi, define for each $k \ge 3$

$s_k = \inf\{\delta : k\text{-SAT can be solved in time } O^*(2^{\delta n})\},$

where $O^*$ hides factors polynomial in the input size. Because a $k$-CNF formula is also a $(k+1)$-CNF formula, $s_3 \le s_4 \le \cdots$, and the limit $s_\infty = \lim_{k \to \infty} s_k$ exists.^[3]

ETH is equivalent to the statement that $s_3 > 0$.^[3] Lokshtanov, Marx and Saurabh's survey states it as: there is a positive real $s$ such that 3-CNF-SAT with parameter $n$ cannot be solved in time $2^{sn}(n+m)^{O(1)}$.^[3] In particular, ETH rules out any $2^{o(n)}(n+m)^{O(1)}$ algorithm. Refuting the hypothesis in the strict sense only requires that, for every $\delta > 0$, some algorithm runs in time $O(2^{\delta n})$. The Anthropic paper notes that its algorithm goes further, giving one uniform algorithm with an explicit $o(n)$ rate.^[20]

History

Impagliazzo, Paturi and Zane's paper "Which problems have strongly exponential complexity?" appeared at FOCS 1998 and in the Journal of Computer and System Sciences in 2001.^[2] Impagliazzo and Paturi's "Complexity of k-SAT" appeared at the 1999 IEEE Conference on Computational Complexity, and its journal version "On the complexity of k-SAT" was published in the same journal in 2001.^[1] Sources differ on how they credit the hypothesis. The Lokshtanov, Marx and Saurabh survey credits ETH and SETH to Impagliazzo, Paturi and Zane, the Anthropic paper attributes ETH to Impagliazzo and Paturi, and OpenAI's announcement describes Impagliazzo, Paturi and Zane as "the original proposers."^[3][18][20] The Anthropic paper also notes that Richard Stearns and Harry Hunt had proposed a hypothesis of this kind in 1990, in "Power indices and easier hard problems."^[20]

The two original papers proved several structural facts that gave the hypothesis its credibility:^[3]

• The statements "$s_k > 0$ for all $k \ge 3$," "$s_k > 0$ for some $k$," "$s_3 > 0$," and "SNP is not contained in SUBEPT" are equivalent. SNP and the related class size-constrained SNP contain $k$-SAT and problems such as Independent Set, Vertex Cover and Clique measured by the number of vertices. Through these reductions, several NP-complete problems are equivalent with respect to solvability in subexponential time.
• Assuming ETH, the sequence $s_k$ increases infinitely often, and $s_k \le s_\infty(1 - d/k)$ for some constant $d > 0$.

The hypothesis is deliberately called a hypothesis rather than a conjecture. In a 2019 essay, Williams recalled Impagliazzo often reminding him: "It's not a Conjecture, it's a Hypothesis! We chose that word for a reason."^[10]

The sparsification lemma

The key technical tool behind ETH is the sparsification lemma of Impagliazzo, Paturi and Zane. In the form given by Lokshtanov, Marx and Saurabh, for every $\varepsilon > 0$ and every clause width $r$ there is a constant $C$ such that any $r$-CNF formula $F$ on $n$ variables can be written as a disjunction $F = Y_1 \lor \cdots \lor Y_t$ with $t \le 2^{\varepsilon n}$, where each $Y_i$ is an $r$-CNF formula in which every variable appears in at most $C$ clauses. The disjunction can be computed in time $2^{\varepsilon n} n^{O(1)}$.^[3]

Because each sparse formula has a number of clauses linear in $n$, the lemma shows that ETH also rules out 3-SAT algorithms running in time $2^{o(m)}$, where $m$ is the number of clauses.^[3] This matters for lower bounds. Many standard NP-hardness reductions from 3-SAT produce instances whose size is linear in the number of clauses, so they carry the $2^{o(n)}$ lower bound over to the target problem.^[3] Calabro, Impagliazzo and Paturi, and later Calabro's dissertation, improved the lemma's bounds, and Dell and coauthors gave a version that preserves the number of satisfying assignments, which both 2026 refutation papers use.^[15][16][20]

Relationship to P versus NP

ETH is a stronger assumption than P ≠ NP. If ETH holds, 3-SAT has no polynomial-time algorithm, so P ≠ NP. Lokshtanov, Marx and Saurabh note that P ≠ NP on its own does not rule out, for example, an $n^{O(\log n)}$-time algorithm for 3-SAT; such an algorithm would contradict ETH.^[3]

The converse does not hold. Refuting ETH would not show P = NP. The Anthropic paper states that its result "does not bear on the P vs NP question directly."^[20] The OpenAI paper explains that running times of the form $2^{o(n)}$ do not survive general polynomial-time reductions, which can blow up the instance size polynomially. Its result therefore does not imply subexponential algorithms for all NP problems, although it does give them for problems with size-preserving reductions to bounded-width SAT.^[16] Leslie Goldberg of the University of Oxford told New Scientist: "This doesn't have a direct impact on P versus NP, so we should not view it as progress towards P versus NP."^[29]

Consequences and uses

ETH and SETH became standard assumptions in exact algorithms, parameterized complexity and fine-grained complexity.^[3][6] A typical lower bound reads "assuming ETH, problem X has no algorithm running in time T." Such a result does not prove that X is hard. It shows that beating T would require a breakthrough in satisfiability algorithms. Lokshtanov, Marx and Saurabh argued that these bounds stay informative even for readers who doubt the hypotheses, because they show that problem-specific ideas are unlikely to help.^[3]

Exact exponential-time algorithms

Under ETH, 3-Coloring, Dominating Set, Independent Set, Vertex Cover and Hamiltonian Path have no $2^{o(n)}$-time algorithms on $n$-vertex graphs. The reason is that standard reductions from 3-SAT produce graphs with a number of vertices linear in the formula size.^[3] Reductions with a polynomial blow-up give weaker bounds; for example, planar Hamiltonian Cycle has no $2^{o(\sqrt{n})}$ algorithm under ETH.^[3]

Parameterized complexity

In parameterized complexity, ETH gives sharper statements than the usual assumption FPT ≠ W^[1]. Chen, Huang, Kanj and Xia showed that, assuming ETH, Clique and Independent Set have no $f(k)n^{o(k)}$-time algorithm for any computable $f$. Their result implies that the trivial $n^{O(k)}$ approach is essentially optimal.^[3][5] Because an FPT algorithm runs in time $f(k)n^{O(1)}$ and Clique is W^[1]-complete, the same bound shows that ETH implies FPT ≠ W^[1].^[3] Many other parameterized algorithms were shown to be optimal in the same sense, and SETH gave matching lower bounds for dynamic programming over tree decompositions. Under SETH, for example, Independent Set and Dominating Set on graphs of treewidth $w$ cannot be solved in time $(2-\varepsilon)^w n^{O(1)}$ and $(3-\varepsilon)^w n^{O(1)}$ respectively.^[3]

Fine-grained complexity of problems in P

SETH also reaches problems that are already solvable in polynomial time. Williams showed in 2005 that SETH implies the Orthogonal Vectors problem needs essentially quadratic time, which started the use of SETH as a hardness assumption for problems in P.^[6][7] Reductions from Orthogonal Vectors and from SAT then gave conditional quadratic lower bounds for Edit Distance (Backurs and Indyk), Longest Common Subsequence, Fréchet distance and approximate graph diameter.^[6][8] Virginia Vassilevska Williams's 2018 survey for the International Congress of Mathematicians describes SETH, 3SUM and All-Pairs Shortest Paths as the main hypotheses of the field.^[6]

Algorithms and circuit lower bounds

Williams's "algorithms to lower bounds" program links faster satisfiability algorithms to circuit lower bounds. In "Improving exhaustive search implies superpolynomial lower bounds" (STOC 2010; SIAM Journal on Computing 2013), Theorem 6.1 states: "If the Exponential Time Hypothesis is false, then $\mathsf{E}^{\mathsf{NP}}$ does not have linear size circuits."^[9] Under this theorem, a refutation of ETH would give a new unconditional circuit lower bound. Williams pointed to the result on 26 October 2026, writing that if the OpenAI claim holds, "E^(NP) does not have linear size circuits!"^[25] The OpenAI paper derives a version as its Corollary 1.4: a language in $\mathsf{E}^{\mathsf{NP}}$ needs more than $c,n\sqrt{\log n}$ gates on infinitely many input lengths.^[16]

Algorithms for k-SAT before 2026

Before October 2026, every published algorithm for 3-SAT ran in time $c^n$ for a constant $c > 1$, and the improvements over brute force shrank as $k$ grew. This was the pattern that motivated SETH.^[3][16]

For counting, the best previous bounds cited in the Anthropic paper were $O(1.6423^n)$ for #3-SAT and $2^{(1-\Theta(1/k))n}$ for #$k$-SAT.^[20]

Doubts before 2026

ETH was widely used but never universally believed. In his 2019 essay "Some estimated likelihoods for computational complexity," Ryan Williams gave a personal estimate of 70% that ETH is true, 25% for SETH and 80% for P ≠ NP. He gave as his main reason that "we simply do not yet have a somewhat-comprehensive understanding of what can be solved via sub-exponential time algorithms," and said researchers "should be a little more skeptical of ETH, and periodically think seriously about how it might be refuted."^[10] In 2016 he refuted a Merlin-Arthur version of SETH with a Merlin-Arthur proof system that certifies the unsatisfiability of $k$-CNF formulas in about $2^{n/2}$ time.^[11][16] The Anthropic paper also lists results showing that a strengthening called Super-Strong ETH fails for random $k$-SAT, and that the set cover conjecture, a relative of SETH, is incompatible with the asymptotic rank conjecture.^[20]

Claimed refutation (2026)

OpenAI manuscript

On 26 October 2026, OpenAI published "The Exponential Time Hypothesis is False" in its public mathematics repository, alongside a manuscript claiming a result in harmonic analysis. The same announcement described a third claimed result, in quantum field theory, whose materials OpenAI withheld at the request of the physics working group.^[18][19] The repository describes its contents as manuscripts produced by "an unnamed internal OpenAI model" and as "raw research data, rather than polished academic papers." It is a continuation of the collection OpenAI first released on 6 October 2026 (see OpenAI Mathematics Collection).^[19] OpenAI said its system found the natural-language disproof on 16 October 2026 and formalized it in Lean on 17 October.^[18] The PDF is dated 17 October 2026 and revised 25 October 2026, and its byline reads only "OpenAI."^[16]

The manuscript's main theorem (Theorem 1.1) claims that for each fixed $k \ge 2$ a deterministic algorithm counts the satisfying assignments of a $k$-CNF formula with $n$ variables and $m$ clauses in

$(n+m)^{O_k(1)}\, 2^{O_k(n \log\log n / \sqrt{\log n})}$

bit operations and polynomial space. It claims the improved bound $2^{O_{k,D}(n/\sqrt{\log n})}$ when $m \le Dn$.^[16] Deciding whether the count is positive solves satisfiability, so the case $k = 3$ would refute ETH. The paper says the result also refutes SETH, #ETH, Gap-ETH and NSETH, along with the randomized versions of ETH and SETH.^[16] The method is algebraic. It uses polynomial interpolation over carefully chosen auxiliary variables, a counting-preserving form of the sparsification lemma, and parity tests drawn from expander-based Tanner codes; an appendix proves the sharpest bounds by tensor contraction.^[16]

The Lean formalization covers a slightly weaker statement. According to the repository's scope document, Lean proves that a deterministic machine exactly counts satisfying assignments of a canonically encoded $k$-CNF in time $(L+1)^{O_k(1)}2^{O_k(n(\log\log n)^2/\sqrt{\log n})}$, where $L$ is the input's bit length. The sharper bounds in the manuscript are not part of that formal statement.^[17]

Anthropic paper

On the evening of 26 October 2026 (US time), Anthropic added a folder named eth to its formal-math GitHub repository. It contains a paper titled "A $2^{o(n)}$ Time Algorithm for 3-SAT," credited to "Claude, Anthropic," together with a Lean 4 formalization.^[20][21] The paper is dated 26 October 2026. The Hexagon preprint server lists it as version 1 of 27 October 2026 under a CC BY 4.0 license, labeled "Primarily AI-generated."^[22] According to the paper's provenance statement, "the core algorithm was found on October 16 by an internal Claude research model with 14M output tokens and no human input," after which Anthropic researchers worked with Claude to improve the presentation. The statement adds that "independently and concurrently, an internal model at OpenAI claims to have proven a similar result."^[20][22]

The paper's main theorem claims a deterministic algorithm that counts the satisfying assignments of a $k$-CNF in which $n$ variables occur, with $m$ clauses, in time

$2^{O(\min\{k^2 n \log\log n/\sqrt{\log n},\; k m/\sqrt{\log m}\})},$

with an absolute constant hidden in the $O$.^[20] The approach views the formula as a graph whose nodes are clauses and whose edges carry shared variables. It recursively rewrites the count as signed sums of tensor network contractions with fewer "edge bits" crossing between parts, using a decomposition of a crossing gadget that starts from the classical eight-square identity.^[20] The paper says its consequences include $O(2^{\delta n})$-time algorithms, for every $\delta > 0$, for Independent Set, Clique, Vertex Cover and Dominating Set on $n$-vertex graphs, and, via Williams's theorem, that $\mathsf{E}^{\mathsf{NP}}$ lacks linear-size Boolean circuits.^[20] In a literature search carried out by Claude, the authors say they found more than 800 papers that prove at least one result only under ETH or a hypothesis implying it.^[20]

The repository README states that the Lean statement file MainResults.lean imports only Mathlib and states, on Mathlib's Turing machines, both that ETH is false and the paper's main counting theorem. The proofs depend only on Lean's three standard axioms, and a stricter check re-verifies them with a second, independently written kernel. The README also cautions that "no machine checks that this file says what the paper says."^[21]

Comparison of the two claims

Both papers stress that the result is asymptotic. The Anthropic README says the result "is purely asymptotic and says nothing about solving formulas in practice." The paper adds that its general approach "seems unlikely to yield any general improvement unless n > 10^7," while brute force is already impractical at about 100 variables.^[20][21] OpenAI said that turning the theoretical advance into practical improvements "will require significant further research."^[18]

Independent examination

OpenAI's announcement said the computer science result "will be verified and shepherded by a group led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego), and Ryan Williams (MIT)." At that group's request, the natural-language proof and the Lean formalization were made public immediately.^[18] OpenAI said the collaborations follow principles of transparency, no academic credit sought by OpenAI, recognition for the group's work, and independence. It described participation as voluntary and unpaid, with no nondisclosure agreements.^[18]

Williams announced the effort on X on 26 October: "An internal model at OpenAI has produced a claimed refutation of ETH! Russell Impagliazzo, Mohan Paturi, and I have been asked to help organize an open and independent examination of this claim." He added that the three had signed no NDAs and would receive no compensation. They had asked OpenAI to release all raw data on ETH, "including PDFs and Lean source," and to sponsor a conference for the affected community, and OpenAI "agreed to both."^[24] Asked about his first reaction, he wrote: "I asked, 'Are you sure?' They replied that they'd verified it in Lean. I said, 'OK but are you sure?'"^[26]

The three organizers published an open letter to the theoretical computer science community. It invites help with two separate efforts: examining the ETH claim, and developing norms for AI-generated results, including early access, conflicts of interest and credit for checking and explaining proofs. The letter says: "Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny and an understanding that others can reconstruct, question, and build upon." It also notes: "If the claim is correct, it will change an important part of theoretical computer science."^[23] The letter lists both the OpenAI materials and Anthropic's "Refutation of ETH" folder among its resources, together with a shared repository for community notes, a feedback form about a proposed virtual meeting before the end of 2026, and a discussion blog.^[23]

Reactions

Williams told TechCrunch that one of his first questions to OpenAI science lead Dan Roberts was whether the result affected any cryptosystems. He said OpenAI "checked, and they were reasonably confident that this didn't ... imply any breaks."^[28]

What a refutation would and would not change

According to the two papers, a confirmed refutation would remove the basis for every lower bound proved only under ETH, SETH, #ETH, Gap-ETH or NSETH.^[16][20] It would also give new unconditional results, such as the circuit lower bound for $\mathsf{E}^{\mathsf{NP}}$ and subexponential algorithms for counting independent sets, proper $q$-colorings and perfect matchings.^[9][16] Many fine-grained lower bounds would survive, because they rest on weaker hypotheses that neither paper claims to refute. The Orthogonal Vectors hypothesis is the main example. It is implied by SETH, and it underlies the bounds for Longest Common Subsequence and regular-expression matching.^[16][20] The OpenAI paper adds that some treewidth and graph-diameter lower bounds also follow from the hypothesis that CNF-SAT with unbounded clause width has no $2^{(1-\delta)n}$ algorithm. The paper notes that its own guarantee holds for each fixed clause width $k$, while that hypothesis allows the width to grow with $n$.^[16]

References

1. ^1 ^2 ^3 ^4 ^5 ^6 ^7Russell Impagliazzo and Ramamohan Paturi. "On the Complexity of k-SAT." *Journal of Computer and System Sciences* 62(2):367-375, 2001. Conference version: "Complexity of k-SAT," IEEE Conference on Computational Complexity, 1999, pp. 237-240. doi.org/...jcss.2000.1727
2. ^1 ^2 ^3Russell Impagliazzo, Ramamohan Paturi and Francis Zane. "Which Problems Have Strongly Exponential Complexity?" *Journal of Computer and System Sciences* 63(4):512-530, 2001. Conference version: FOCS 1998, pp. 653-662. doi.org/...jcss.2001.1774
3. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12 ^13 ^14 ^15 ^16 ^17 ^18 ^19 ^20 ^21 ^22 ^23Daniel Lokshtanov, Dániel Marx and Saket Saurabh. "Lower bounds based on the Exponential Time Hypothesis." *Bulletin of the EATCS* 105, 2011. sites.cs.ucsb.edu/...surveyETH.pdf
4. ^1 ^2Chris Calabro, Russell Impagliazzo and Ramamohan Paturi. "The Complexity of Satisfiability of Small Depth Circuits." IWPEC 2009, Lecture Notes in Computer Science 5917, pp. 75-85. doi.org/...978-3-642-11269-0_6
5. ^Jianer Chen, Xiuzhen Huang, Iyad A. Kanj and Ge Xia. "Strong computational lower bounds via parameterized complexity." *Journal of Computer and System Sciences* 72(8):1346-1367, 2006. doi.org/...j.jcss.2006.04.007
6. ^1 ^2 ^3 ^4 ^5Virginia Vassilevska Williams. "On some fine-grained questions in algorithms and complexity." Proceedings of the International Congress of Mathematicians, 2018. people.csail.mit.edu/...eccentri.pdf
7. ^Ryan Williams. "A new algorithm for optimal 2-constraint satisfaction and its implications." *Theoretical Computer Science* 348(2-3):357-365, 2005. doi.org/...j.tcs.2005.09.023
8. ^Arturs Backurs and Piotr Indyk. "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)." *SIAM Journal on Computing* 47(3):1087-1097, 2018. doi.org/...15M1053128
9. ^1 ^2Ryan Williams. "Improving Exhaustive Search Implies Superpolynomial Lower Bounds." STOC 2010; *SIAM Journal on Computing* 42(3):1218-1244, 2013 (Theorem 6.1). cs.cmu.edu/...improved-algs-lbs2.pdf
10. ^1 ^2R. Ryan Williams. "Some Estimated Likelihoods for Computational Complexity." In *Computing and Software Science*, Lecture Notes in Computer Science 10000, 2019. people.csail.mit.edu/...likelihoods.pdf
11. ^Ryan Williams. "Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation." arXiv:1601.04743, 2016 (CCC 2016). arxiv.org/...1601.04743
12. ^Uwe Schöning. "A probabilistic algorithm for k-SAT and constraint satisfaction problems." 40th IEEE Symposium on Foundations of Computer Science, 1999, pp. 410-414. doi.org/...SFFCS.1999.814612
13. ^Ramamohan Paturi, Pavel Pudlák, Michael E. Saks and Francis Zane. "An improved exponential-time algorithm for k-SAT." *Journal of the ACM* 52(3):337-364, 2005. doi.org/...1066100.1066101
14. ^Timon Hertli. "3-SAT Faster and Simpler: Unique-SAT Bounds for PPSZ Hold in General." arXiv:1103.2165, 2011 (FOCS 2011; *SIAM Journal on Computing* 2014). arxiv.org/...1103.2165
15. ^1 ^2Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman and Martin Wahlén. "Exponential Time Complexity of the Permanent and the Tutte Polynomial." *ACM Transactions on Algorithms* 10(4), 2014. doi.org/...2635812
16. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12 ^13 ^14 ^15 ^16 ^17 ^18 ^19 ^20 ^21 ^22OpenAI. "The Exponential Time Hypothesis is False." Manuscript dated 17 October 2026, revised 25 October 2026. github.com/...paper.pdf
17. ^1 ^2OpenAI. "The Exponential Time Hypothesis is False" (Lean formalization scope, document 378). github.com/...378.md
18. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8OpenAI. "Working with academic communities to build scientific understanding." 26 October 2026. openai.com/...erstanding-with-academic-communities
19. ^1 ^2OpenAI. openai/math repository README and release history (entry for 26 October 2026). github.com/...history.md
20. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12 ^13 ^14 ^15 ^16 ^17 ^18 ^19 ^20 ^21 ^22Claude (Anthropic). "A 2^o(n) Time Algorithm for 3-SAT." Paper dated 26 October 2026. github.com/...paper.pdf
21. ^1 ^2 ^3 ^4Anthropic. anthropics/formal-math, `eth` folder README. github.com/...eth
22. ^1 ^2 ^3Hexagon. "A 2^o(n) Time Algorithm for 3-SAT," hexagon:2610.00577, version 1, 27 October 2026. hexagonmath.org/2610.00577v1
23. ^1 ^2 ^3Russell Impagliazzo, Ramamohan Paturi and Ryan Williams. Letter to the theoretical computer science community on the ETH claim, October 2026. docs.google.com/...edit
24. ^Ryan Williams (@rrwilliams). Thread on X, 26 October 2026. x.com/...2114833319431209352
25. ^Ryan Williams (@rrwilliams). Reply on X about circuit lower bounds, 26 October 2026. x.com/...2114838056608174358
26. ^Ryan Williams (@rrwilliams). Reply on X, 27 October 2026. x.com/...2114935153466479100
27. ^Mary McCue Bell. "Did AI just solve a 30-year-old computer science puzzle? Experts are checking." *The Washington Times*, 27 October 2026. washingtontimes.com/...exponential-time-hypothesis
28. ^1 ^2 ^3Tim Fernholz. "Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?" *TechCrunch*, 27 October 2026. techcrunch.com/...e-hypothesis-what-does-that-mean
29. ^1 ^2 ^3 ^4 ^5Chris Stokel-Walker. "AI refutes 30-year-old mathematical assumption in computer science." *New Scientist*, 27 October 2026. newscientist.com/...assumption-in-computer-science
30. ^Lance Fortnow (@fortnow). Posts on X, 27 October 2026. x.com/...2114875562623635783
31. ^Scott Aaronson. "Podcasts about the Topic: Part II." *Shtetl-Optimized*, 26 October 2026. scottaaronson.blog
32. ^Ben Shimkus. "What smart people are saying about OpenAI's Exponential Time Hypothesis claim." *Business Insider*, 27 October 2026. businessinsider.com/...ial-time-hypothesis-2026-10