[#P3140] Strong Exponential Time Hypothesis

Problem. For every \(\varepsilon>0\), does there exist \(k\ge3\) such that \(k\)-SAT on \(n\) variables cannot be decided in time \(O((2-\varepsilon)^n)\) by a deterministic algorithm?

Agent access

Work on this problem in ChatGPT

Definitions and notation

1Context

Known frontier: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Open boundary: The unrestricted quantified lower bound remains unproved and undisproved.

2Problem setup

Definition 1 (k-SAT). Satisfiability of a CNF formula with at most k literals per clause.

Definition 2 (deterministic running time). Worst-case time as a function of the number n of variables, with polynomial factors absorbed.

Remark 1. SETH says the base of the best exponential-time SAT algorithm approaches 2 as clause width grows. It is a precise hypothesis used to derive conditional lower bounds across algorithms.

3What counts as a solution

Prove the quantified lower bound in a standard deterministic machine model.
Or give one ε>0 and algorithms solving k-SAT in O((2−ε)^n) for every k.

1Status

What counts as a solution

Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Exact unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.^[1][2]

1Packet records

Show recorded summaries

Record	Kind	Assessment
OPEN as checked on 2026-08-01. Strongest checked neighboring result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Exact unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 OPEN as checked on 2026-08-01. Strongest checked neighboring result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Exact unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.^[1][2] Relevance to this problem This is the dated publication status for the canonical target Strong Exponential Time Hypothesis. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. The exact unresolved remainder is: The unrestricted quantified lower bound remains unproved and undisproved. A complete resolution must meet the following acceptance conditions: - Prove the quantified lower bound in a standard deterministic machine model. - Or give one ε>0 and algorithms solving k-SAT in O((2−ε)^n) for every k. Open full record →
Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 2 Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence.^[1][2] Relevance to this problem Locates the present research frontier immediately below Strong Exponential Time Hypothesis. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. This leaves the following boundary unresolved: The unrestricted quantified lower bound remains unproved and undisproved. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.^[1][2] Relevance to this problem Documents why Strong Exponential Time Hypothesis was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - Strong Exponential Time Hypothesis open 2026 - SETH k-SAT base 2 current algorithms The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved. Related: Claim 1 Open full record →
The unrestricted quantified lower bound remains unproved and undisproved.	Trace	Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 2 The unrestricted quantified lower bound remains unproved and undisproved. Relevance to this problem Turns the remaining uncertainty in Strong Exponential Time Hypothesis into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: The unrestricted quantified lower bound remains unproved and undisproved. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Prove the quantified lower bound in a standard deterministic machine model. - Or give one ε>0 and algorithms solving k-SAT in O((2−ε)^n) for every k. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence. Exact unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.

Equivalent-formulation queries: Strong Exponential Time Hypothesis open 2026; SETH k-SAT base 2 current algorithms
Strongest checked neighboring result: Improved algorithms exist for every fixed k, and circuit lower bounds or restricted-model SAT lower bounds give partial evidence.
Exact unresolved remainder: The unrestricted quantified lower bound remains unproved and undisproved.

How the 4 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemStrong Exponential Time Hypothesis

All 3 recorded relations between these records and the problem

2See also

Multiplicative complexity of the six-bit threshold-at-least-three functiontheoretical computer science
Polynomial determinization of two-way finite automatatheoretical computer science
Logarithmic DFA separation of binary wordstheoretical computer science

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Strong Exponential Time Hypothesis.” TheoremDB. P3140. Problem statement; statement text SHA-256 033ba478b32da1587d771fe582034d860fac31f42c67ab2be349775b88021bb1. https://theoremdb.org/statement/?ref=P3140

BibTeX

@misc{theoremdb-problem-033ba478b32da1587d771fe582034d860fac31f42c67ab2be349775b88021bb1,
  title = {{Strong Exponential Time Hypothesis}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 033ba478b32da1587d771fe582034d860fac31f42c67ab2be349775b88021bb1},
  url = {https://theoremdb.org/statement/?ref=P3140}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of August 1, 2026.

1Lean verification

1References

Packet source. Russell Impagliazzo and Ramamohan Paturi, “On the Complexity of k-SAT”. Journal of Computer and System Sciences 62(2) (2001), 367-375. DOI 10.1006/jcss.2000.1727. definition and consequences. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Introduces the exponential-time hypothesis framework and the limiting k-SAT constant.Also cited at R. Impagliazzo and R. Paturi, On the complexity of k-SAT, Journal of Computer and System Sciences 62 (2001). definition and consequences.Source used to assess the problem's recorded status.For Strong Exponential Time Hypothesis: This is the dated publication status for the canonical target Strong Exponential Time Hypothesis.Source named by the research packet.
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane, “Which Problems Have Strongly Exponential Complexity?”. Journal of Computer and System Sciences 63(4) (2001), 512-530. DOI 10.1006/jcss.2001.1774. sparsification lemma and consequences. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Supplies the sparsification machinery underlying the modern SETH formulation.Source used to assess the problem's recorded status.For Strong Exponential Time Hypothesis: Supplies the sparsification machinery underlying the modern SETH formulation.

Original TheoremDB editorial statement and source synthesis; external works are used for citation only.

[#P3140] Strong Exponential Time Hypothesis

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance