TOPICS
Search

Exponential Time Hypothesis


The exponential time hypothesis (ETH) asserts an exponential lower bound for deterministic algorithms deciding 3SAT. Let n count the variables and L denote the input length, and use O for big-O notation, so that L^(O(1)) denotes a factor bounded by a fixed power of L. Formally, ETH asserts that there is a constant epsilon>0 such that no deterministic algorithm decides 3SAT in time

 2^(epsilonn)L^(O(1))

(Impagliazzo and Paturi 2001). In particular, it rules out a running time of 2^(o(n))L^(O(1)), where o(n) denotes a quantity whose ratio to n tends to 0 (little-o notation).

A 3SAT instance is a conjunctive normal form formula with at most three literals per clause. More generally, k-SAT allows at most k literals per clause. Equivalently, for each fixed k>=3, there are constants c>0 and epsilon>0 such that no deterministic algorithm solves k-SAT with at most cn clauses in time 2^(epsilonn)L^(O(1)) (Impagliazzo and Paturi 2001, Impagliazzo et al. 2001). Thus the hypothesis distinguishes among superpolynomial running times, rather than merely asserting that 3SAT is not solvable in polynomial time. ETH implies a negative answer to the P versus NP problem, but the converse is not known.

OpenAI (2026a) reported a deterministic algorithm that, for each fixed k>=2, counts the satisfying assignments of a conjunctive normal form formula with at most k literals per clause. In the bound below, n is the number of variables, m is the number of clauses, and O_k is big-O notation whose implicit constants and asymptotic thresholds may depend on the fixed parameter k, but not on n or m. The algorithm uses polynomial space and has bit complexity

 (n+m)^(O_k(1))2^(O_k(nlnlnn/sqrt(lnn))).

The documented Lean bound instead has exponent O_k(n(lnlnn)^2/sqrt(lnn)), which is also o(n). Either bound would refute ETH, but neither would establish that P equals NP. An internal OpenAI model supplied the reported proof and Lean formalization. Impagliazzo et al. (2026) invited community examination of the OpenAI claim and explicitly distinguished their involvement from certification of the proof. An external audit of OpenAI's Lean formalization reported rebuilding its 3,977-module development for the weaker bound, finding only Lean's three standard axioms, and comparing the proved statement and its definitions with the formal target (Zhao 2026). The statement readings used Claude models. The correspondence with standard Turing machines and input encodings was not formally checked. Busnello (2026) also reported acceptance of OpenAI's formal proof by Lean's default kernel in an external comparator run. O'Donnell (2026) presents an LLM-assisted exposition of OpenAI's argument using exact evaluation of permanents of rational matrices with a bounded number of nonzero entries in each row and column. Kintali (2026) presents a simplified 3SAT decision argument using polynomial interpolation. Independent specialist confirmation of the complete mathematical claim had not been reported as of Nov. 1, 2026.

Claude (2026) reported a separate deterministic algorithm for counting satisfying assignments of k-SAT formulas in time 2^(O_k(nlnlnn/sqrt(lnn))) for each fixed k>=1. The accompanying Lean statement includes this bound on a deterministic Turing machine. It covers formulas with n>=4 variables and at least two clauses, with no repeated clauses and every variable occurring. An internal research Claude model at Anthropic discovered the algorithm, and AI models wrote its formalization. In addition to the project's automated checks, Busnello (2026) reported external acceptance of the formal proof by both Lean's default kernel and nanoda. Both main declarations depended only on Lean's three standard axioms. The check did not establish correspondence with the paper or verify the simulation and formula rewriting that connect its machine model to the usual formulation of ETH. Independent specialist confirmation of the complete claim had not been reported as of Nov. 1, 2026.


See also

3SAT, Computational Complexity, P Versus NP Problem, Satisfiability Problem

Explore with Wolfram|Alpha

References

Busnello, L. A. "Independent Replication of Both ETH Proofs, and a Finite Range Where the SubexponentialSAT Bound's Exponential Factor Sits Above 2^n with A=1." Oct. 31, 2026. https://doi.org/10.5281/zenodo.23836157.Claude. "A 2^(o(n)) Time Algorithm for 3-SAT." Oct. 26, 2026. https://github.com/anthropics/formal-math/blob/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth/paper.pdf.Impagliazzo, R. and Paturi, R. "On the Complexity of k-SAT." J. Comput. Syst. Sci. 62, 367-375, 2001. https://doi.org/10.1006/jcss.2000.1727.Impagliazzo, R.; Paturi, R.; and Williams, R. "ETH Refutation: Examination and Discussion." Oct. 26, 2026. https://ethdiscussion.blog/2026/10/26/eth-refutation-examination-and-discussion/.Impagliazzo, R.; Paturi, R.; and Zane, F. "Which Problems Have Strongly Exponential Complexity?" J. Comput. Syst. Sci. 63, 512-530, 2001. https://doi.org/10.1006/jcss.2001.1774.Kintali, S. "A Simplified Proof of ETH Is False." Oct. 26, 2026. https://shivakintali.github.io/papers/ETH.pdf.O'Donnell, R. "Some Exposition of 'The Exponential Time Hypothesis Is False'." Oct. 29, 2026. https://www.cs.cmu.edu/~odonnell/some_eth_false_exposition.pdf.OpenAI. "The Exponential Time Hypothesis Is False." Oct. 25, 2026a. https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf.OpenAI. "Working with Academic Communities to Build Scientific Understanding." Oct. 26, 2026b. https://openai.com/index/building-scientific-understanding-with-academic-communities/.Zhao, B. "Family 378: Subexponential #k-SAT (Exponential Time Hypothesis)." Oct. 28, 2026. https://github.com/Beltran12138/oai-math-recheck/blob/45651629b2335b108f5c113d53a57ee3db06031c/families/378/README.md.

Cite this as:

Weisstein, Eric W. "Exponential Time Hypothesis." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ExponentialTimeHypothesis.html

Subject classifications