Papex

Problem · Computer science · since 1999 · Claimed

Exponential time hypothesis

Does solving 3-SAT really require exponential time?

Summary

The hypothesis that 3-SAT cannot be solved in subexponential time is unproven; if true, it would imply P ≠ NP and that many known algorithms are close to optimal.

AI-assisted claims

Disproof claimed · 26 Oct 2026

A 2^o(n) Time Algorithm for 3-SAT

“We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in 2^o(n) time. Our algorithm in fact solves the harder problem #3-SAT, providing a count of the number of satisfying assignments.”

By
Anthropic
AI involvement
The core algorithm was found on October 16 by an internal Claude research model with 14M output tokens and no human input. Anthropic researchers worked with Claude to improve the presentation, resulting in this paper. Independently and concurrently, an internal model at OpenAI claims to have proven a similar result.
Model
an internal Claude research model, as stated
Where
anthropics/formal-math repository
Write-up
Natural language, published by the source
Formal proof
Lean 4, published by the source
Repository
anthropics/formal-math at 16a5ce4 · read 21 Nov 2026
Statement file
eth/MainResults.lean
Source last read
27 Oct 2026

Disproof claimed · 26 Oct 2026

The Exponential Time Hypothesis is false

“Surprisingly, our system has recently proved that the ETH is false, a result that was subsequently verified in Lean.”

By
OpenAI
AI involvement
Our AI found its natural language disproof for the ETH on October 16th, 2026 and then subsequently we formalized the result in Lean on October 17th, 2026
Model
internal OpenAI models, as stated
Where
OpenAI announcement
Write-up
Natural language, published by the source
Formal proof
Lean 4, published by the source
Repository
openai/math at 4eaee87 · read 21 Nov 2026
Statement file
lean/ComparatorChallenges/SubexponentialSAT.lean
Verifying
A group led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego) and Ryan Williams (MIT)
Source last read
27 Oct 2026

Note: Refuting ETH does not resolve P vs NP.

Checks

1 response · 1 comment

  • 28 Oct 2026 · Response · Chelsea Anne McElveen, in the community repository oai-math-revised: “NOTES.md — commentary: an executable model of Sections 2.3–2.7 checked against brute force at n ≤ 14; two structural remarks on the Section 2.7 construction … Does not change the TeX source or the manuscript's claims. No error in the manuscript is asserted.” Source
  • 26 Oct 2026 · Commentary · Russell Impagliazzo, Ramamohan Paturi and Ryan Williams (ETH examination blog): Announces an open community examination of OpenAI's claimed refutation that the three signatories help organize; it reports no findings. “Our involvement should not be taken as certification of the claim.” Source

Claims as their sources state them. Listing a claim is not a check by Papex; the status stays the source’s.

All AI-assisted claims

Why it is open

In k-SAT the input is a formula in conjunctive normal form (an AND of clauses, each an OR of literals) whose clauses each contain at most k literals; trying every assignment of n variables takes about 2^n steps [6]. Russell Impagliazzo and Ramamohan Paturi defined s_k as the infimum of the constants δ for which k-SAT can be solved in time 2^(δn), and stated the exponential time hypothesis (ETH) as s_k > 0 for every k ≥ 3: 3-SAT has no subexponential algorithm [1]. Their paper was received by the journal in June 1999 and published in 2001 [1].

The strong exponential time hypothesis (SETH) says that s_k tends to 1 as k grows: for every ε > 0 there is a k such that k-SAT cannot be solved in time 2^((1−ε)n) [6]. Surveys attribute both hypotheses, in the form now used, to Impagliazzo, Paturi and Francis Zane, SETH being the stronger [4, 6].

ETH is a stronger assumption than P ≠ NP: Daniel Lokshtanov, Dániel Marx and Saket Saurabh point out that P ≠ NP does not rule out, for example, an n^(O(log n)) algorithm for 3-SAT, and that excluding such algorithms needs a stronger hypothesis [4] (see the Papex page on P versus NP; a related question about short proofs is NP versus co-NP). ETH would be refuted by algorithms for 3-SAT running in time 2^(δn) for every δ > 0 [1], and SETH by a single δ < 1 that works for every k [4].

No prize or body sets the terms of a resolution. The status here follows Wikipedia's list of unsolved problems in computer science, which asks separately whether ETH and SETH are true [14].

What is known

Consequences of ETH (1999–2011). Impagliazzo and Paturi showed that, if ETH holds, s_k increases infinitely often as k grows, and s_k ≤ (1 − d/k)s_∞ for some constant d > 0, where s_∞ is the limit [1]. Impagliazzo, Paturi and Zane's sparsification lemma rewrites any k-CNF formula as a disjunction of at most 2^(εn) formulas, each with O(n) clauses [2]. With it they showed that k-SAT, k-colourability, k-set cover, independent set, clique and vertex cover are complete for a class of search problems called SNP under reductions that preserve subexponential time, so a subexponential algorithm for any one of them would give one for all [2]; Lokshtanov and colleagues read such equivalences as strengthening the credibility of ETH [4]. Assuming ETH, there is no 2^(o(n)) algorithm for 3-colouring, dominating set, independent set, vertex cover or Hamiltonian path on n-vertex graphs, and no f(k)·n^(o(k)) algorithm for finding a clique of size k [4]. Cygan and colleagues showed that exhaustive search can be beaten for hitting set, set splitting and not-all-equal SAT, with bounded set or clause size, if and only if SETH fails [4].

Algorithms for 3-SAT (1985–2026). The first non-trivial bound, 1.619^n, came from a deterministic branching algorithm of Burkhard Monien and Ewald Speckenmeyer, and Uwe Schöning's random-walk algorithm runs in (4/3)^n [9]. The PPSZ algorithm of Paturi, Pavel Pudlák, Michael Saks and Zane sets variables in random order, inferring values where it can and guessing otherwise [11]. It solves 3-SAT on formulas with a unique satisfying assignment (Unique-3-SAT) in time 2^((2 ln 2 − 1)n + o(n)), about 2^(0.386n) [3]. Timon Hertli showed that PPSZ's bounds for unique formulas also hold for general 3-SAT, which he states as O(1.308^n) [5]. In 2019 Thomas Dueholm Hansen, Haim Kaplan, Or Zamir and Uri Zwick introduced biased-PPSZ, the first improvement over PPSZ for every k > 3 [9]. Dominik Scheder then proved that the original PPSZ is exponentially faster than previously known for all k ≥ 3: O(1.306973^n) for Unique-3-SAT, against O(1.306995^n) for biased-PPSZ and O(1.3070319^n) before it [11]. A lifting theorem of Scheder and John Steinberger turns any such improvement for unique formulas into a smaller one for general formulas [12]. A July 2026 preprint by Tao Jiang and Shaowei Cai, not peer reviewed, re-analyses Scheder's argument and reports O(1.307031578^n) for general 3-SAT, against 1.307031594^n that they derive from Scheder's original analysis with the same lifting theorem; the authors write that, to their knowledge, this is the best known worst-case randomised bound [13].

Limits of PPSZ (2017). The saving of such an algorithm is the largest γ for which it succeeds with probability at least 2^(−(1−γ)n). Pudlák, Scheder and Navid Talebanfard constructed uniquely satisfiable k-CNF formulas on which a weak form of PPSZ saves at most (2 + ε)/k, optimal up to a constant factor since PPSZ is known to save at least (π² + o(1))/(6k), and formulas on which strong PPSZ saves at most O(log k / k) [7].

Fine-grained consequences. SETH is the basis of conditional lower bounds for problems that already have polynomial-time algorithms, such as edit distance, longest common subsequence and graph diameter [6]. Ryan Williams showed that SETH rules out a truly subquadratic algorithm for orthogonal vectors (OV), which asks whether two of n Boolean vectors have no 1 in a common coordinate [6]. Arturs Backurs and Piotr Indyk showed that an O(n^(2−δ)) algorithm for edit distance would give a 2^((1−ε)N) algorithm for CNF-SAT on N variables, violating SETH [8]; Wikipedia lists strongly subquadratic edit distance as an open question that "is only possible if the strong exponential time hypothesis is false" [14].

Main approaches

Faster satisfiability algorithms. Refuting either hypothesis needs an algorithm [1, 4]. Strongest evidence: in a 2019 opinion essay giving personal estimates of 70% for ETH and 25% for SETH, Williams writes that the reach of subexponential algorithms is not yet well understood, and, against SETH, that exponential-time algorithms have often cut c^n to (c − δ)^n for NP-complete problems, with no good reason why k-SAT should be immune [10]; Hansen and colleagues believe their analysis "only scratches the surface" [9]. Main difficulty: Hansen and colleagues call their own gain for 3-SAT "relatively small" and Hertli's earlier one "tiny" [9]; PPSZ has hard instances [7]; and the savings of known k-SAT algorithms vanish as k grows [6].

Conditional lower bounds. Fine-grained complexity takes ETH or SETH as a hypothesis and uses reductions that track exact running times to explain why algorithms have not improved [4, 6]. Strongest evidence: many of these lower bounds match the best known algorithms [4]. Main difficulty: they rest on unproven hypotheses, and many SETH-based results actually rest on OV, which may stay hard even if SETH is false; no reduction from OV to CNF-SAT is known [6, 10].

Nondeterministic and probabilistic proofs. The nondeterministic SETH (NSETH) of Carmosino and colleagues says that for every δ < 1 there is a k for which no nondeterministic algorithm can prove k-CNF formulas unsatisfiable in time 2^(δn) [10]. Strongest evidence: showing that a formula is unsatisfiable seems to need a lot of nondeterministic time, and NSETH explains why some reductions are missing: a tight reduction from OV to 3SUM or all-pairs shortest paths would refute it [6]. Main difficulty: Williams showed that with a randomised verifier unsatisfiability of formulas of size 2^(o(n)) can be certified in 2^(n/2 + o(n)) time; derandomising this "seems challenging", and Williams gives NSETH only 15% [6, 10].

Open sub-questions

  1. Lossless lifting. Can the general 3-SAT bound reach the Unique-3-SAT bound O(1.306973^n), so that lifting from unique to general formulas loses nothing for k = 3 [11, 12, 13]?
  2. Hard instances for strong PPSZ. Are there k-CNF formulas on which strong PPSZ saves only O(1/k), removing the log k factor left by Pudlák, Scheder and Talebanfard [7]?
  3. Biased-PPSZ without scaffolding. How much does an analysis of biased-PPSZ that drops the preliminary set of disjoint clauses improve the 3-SAT exponent, as its authors expect [9]?
  4. From SAT back to orthogonal vectors. Would a (2 − ε)^n algorithm for CNF-SAT give a truly subquadratic algorithm for orthogonal vectors? No such reduction is known [6].
  5. Derandomising the 2^(n/2) proofs. Can Williams's randomised certificates of unsatisfiability be turned into nondeterministic proofs checkable in time (2 − ε)^n for k-CNF formulas, refuting NSETH [6, 10]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Impagliazzo, R. & Paturi, R. (2001). On the complexity of k-SAT. Journal of Computer and System Sciences 62(2), 367–375. 10.1006/jcss.2000.1727 · Checked 16 Oct 2026
  2. Impagliazzo, R., Paturi, R. & Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63(4), 512–530. 10.1006/jcss.2001.1774 · Checked 16 Oct 2026
  3. Paturi, R., Pudlák, P., Saks, M. E. & Zane, F. (2005). An improved exponential-time algorithm for k-SAT. Journal of the ACM 52(3), 337–364. 10.1145/1066100.1066101 · Checked 16 Oct 2026
  4. Lokshtanov, D., Marx, D. & Saurabh, S. (2011). Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS 105, 41–72. Source · Checked 16 Oct 2026
  5. Hertli, T. (2014). 3-SAT faster and simpler: Unique-SAT bounds for PPSZ hold in general. SIAM Journal on Computing 43(2), 718–729. 10.1137/120868177 · Checked 16 Oct 2026
  6. Vassilevska Williams, V. (2015). Hardness of easy problems: basing hardness on popular conjectures such as the Strong Exponential Time Hypothesis. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), LIPIcs 43, 17–29. 10.4230/LIPIcs.IPEC.2015.17 · Checked 16 Oct 2026
  7. Pudlák, P., Scheder, D. & Talebanfard, N. (2017). Tighter hard instances for PPSZ. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), LIPIcs 80, 85. 10.4230/LIPIcs.ICALP.2017.85 · Checked 16 Oct 2026
  8. Backurs, A. & Indyk, P. (2018). Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM Journal on Computing 47(3), 1087–1097. 10.1137/15M1053128 · Checked 16 Oct 2026
  9. Hansen, T. D., Kaplan, H., Zamir, O. & Zwick, U. (2019). Faster k-SAT algorithms using biased-PPSZ. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), 578–589. 10.1145/3313276.3316359 · Checked 16 Oct 2026
  10. Williams, R. R. (2019). Some estimated likelihoods for computational complexity. In Computing and Software Science, Lecture Notes in Computer Science, Springer, 9–26. An opinion essay. 10.1007/978-3-319-91908-9_2 · Checked 16 Oct 2026
  11. Scheder, D. (2024). PPSZ is better than you think. TheoretiCS 3, theoretics:9832; conference version in FOCS 2021. 10.46298/theoretics.24.5 · Checked 16 Oct 2026
  12. Scheder, D. & Steinberger, J. (2024). PPSZ for general k-SAT and CSP: making Hertli's analysis simpler and 3-SAT faster. computational complexity 33(2), 13. 10.1007/s00037-024-00259-y · Checked 16 Oct 2026
  13. Jiang, T. & Cai, S. (2026). A better analysis for PPSZ for 3-SAT. Preprint, arXiv:2607.10697 (version 1, 12 July 2026), not peer reviewed. Source · Checked 16 Oct 2026
  14. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Status
Claimed
Claimed by
OpenAI
Where
Working with academic communities to build scientific understanding
Date
26 Oct 2026
Verifying
A group led by Russell Impagliazzo (UC San Diego), Ramamohan Paturi (UC San Diego) and Ryan Williams (MIT)
Checked
27 Oct 2026

The status is the source’s. Papex does not decide whether a problem is solved.

Status history

  1. Claimed · OpenAI · Working with academic communities to build scientific understanding · Checked 27 Oct 2026
  2. Open · Wikipedia · Unsolved problems in computer science · Checked 29 Sep 2026

Records on this problem

No public record addresses this problem yet.

More in Computing