Theoretical computer science · exact exponential algorithms · SAT complexity · fine-grained complexity

Exponential Time Hypothesis and Strong ETH

Collaboration beta

Must satisfiability require exponential time in the worst case, and does the best possible base for fixed-width SAT approach two as the clause width grows?

ETH : s_{3} > 0, SETH : \lim_{k \to \infty} s_{k} = 1

Known results and sources

ETH asks for a positive exponential lower bound for 3-SAT; SETH asks whether the optimal fixed-width SAT exponent tends to one. Both remain unresolved.

Research problem

Exact mathematical statement

For each fixed integer $k\geq 2$ , let

s_k=\inf\left\{c\geq 0: \; k\text{-SAT on }n\text{ variables is solvable in }O^*(2^{cn})\right\},

where $O^*(\cdot)$ suppresses polynomial factors. The deterministic Exponential Time Hypothesis and Strong Exponential Time Hypothesis are

\mathrm{ETH}: \quad s_3>0,\qquad\qquad \mathrm{SETH}: \quad \lim_{k\to\infty}s_k=1.

Equivalently, SETH says that for every $\varepsilon>0$ , some fixed clause width $k$ admits no algorithm with running time $O^*((2-\varepsilon)^n)$ . SETH implies ETH. A $2^{o(n)}$ -time algorithm for 3-SAT would disprove both, while a uniform base-below-two algorithm across all fixed widths could disprove SETH without disproving ETH. The source explicitly states that both hypotheses remain unresolved.

Problem infographic

Problem at a glance

A wide scientific explainer defines the SAT exponent s_k as the infimum c permitting O-star of 2 to the cn time, states ETH as s_3 greater than zero and SETH as the limit of s_k equal to one, and distinguishes three resolution outcomes: proving SETH, disproving ETH with a subexponential 3-SAT algorithm, or proving ETH while disproving SETH. A lower band shows clause width increasing toward the base-two boundary and labels both hypotheses open. — ETH and SETH are related but not identical: SETH implies ETH, a subexponential 3-SAT algorithm would refute both, and a uniform base improvement for every fixed width could refute SETH without refuting ETH. No such resolution is known.

Current mathematical picture

Where work on Exponential Time Hypothesis and Strong ETH stands

Open problem

Selected route highlights from the current work. This is not yet a complete mathematical inventory.

Useful failureSource-reported limitation

Within edge-dependent invertible two-by-two transformations that turn every exact-core NAE_3 and EQ_4 tensor into a standard matchgate signature, no new basis survives. The retained reductions and barriers do not prove a lower bound or supply a subexponential algorithm. A resolution still requires a genuinely subexponential algorithm for an ETH-equivalent core, a uniform base-saving algorithm for the direct SETH target, or an unrestricted complexity lower-bound breakthrough.

Route status · Narrowed route

Main reductionParsimonious exact-regular hypergraph core

The source gives a linear-size, solution-count-preserving reduction from signed NAE-3-SAT to 2-colorability of exactly 4-regular, linear, 3-uniform hypergraphs with explicit size formulas.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeDetermine the six-coordinate quadratic phase rank chi_2(6), including both six- and seven-phase cases.Task status · Work already reported in progress

Research-record correctionResearch-record correction

We corrected supporting details in the research record. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Exponential Time Hypothesis and Strong ETH in numbers

2.5kretained lines of mathematical investigation2,470 in the current working snapshot

Argument development: 2,043 · 83%
Explored or eliminated routes: 34 · 1%
Computational analysis: 119 · 5%
Open obligations: 90 · 4%
Definitions and setup: 184 · 7%

9selected mapped statements1routes investigated3open questions2contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byRussell Impagliazzo, Ramamohan PaturiProposed2001Status checkedAug 7, 2026

Source recordedAug 7, 2026

Recommended next task

Find a subexponential collective evaluation of the correlated quadratic-sector family or equivalent unbounded phase decomposition.

Suggested move: Analyze the image and fibres of the shared quadratic profile map before expanding sign sectors, seek a transform or contraction with o(N) state dimension, and test every proposed compression on the U, W, affine-plane, and 2·3^r benchmark families.

What would count as progress

Retain an exact proof or counterexample for the stated subproblem.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

13 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded

Narrowed routeSource-reported limitation

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Find a subexponential collective evaluation of the correlated quadratic-sector family or equivalent unbounded phase decomposition.Suggested move: Analyze the image and fibres of the shared quadratic profile map before expanding sign sectors, seek a transform or contraction with o(N) state dimension, and test every proposed compression on the U, W, affine-plane, and 2·3^r benchmark families.

Ready to work on

Determine whether fixed-weight Pfaffian sectors collapse for the exact incidence signatures despite the universal all-weight barrier.Suggested move: Express the full surface-sector family at the single weights -1/3 or a cubic root of unity and search for relations forced by exact bidegrees, girth, and uniform local signatures, checking all mandatory cancellation benchmarks.

Ready to work on

Determine the six-coordinate quadratic phase rank chi_2(6), including both six- and seven-phase cases.Suggested move: Enumerate the 81-row zero-set layer for each of the five canonical rank-four six-frequency supports, test quadratic support separation, then solve the exact value equations for survivors and classify seven frequencies if needed.

Work already reported in progress

Sourced mathematical context

The known mathematical landscape

Context collected Aug 7, 2026

Current statusOpen problem

Both deterministic uniform ETH and SETH remain open. ETH rules out subexponential-time algorithms for 3-SAT, while the stronger SETH asserts that the limiting k-SAT exponent is one. Extensive sparsification, equivalence, and fine-grained lower-bound results are conditional consequences, and the 2026 restricted proof-system theorem does not resolve the unrestricted algorithmic hypotheses.

[5][6][7]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026
Peer reviewedEfremenko and Itsykson proved SETH-shaped lower bounds for bounded-depth resolution over parity axioms. The theorem is confined to restricted proof systems and does not resolve algorithmic SETH.[7]
2018
Peer reviewedBackurs and Indyk proved that a strongly subquadratic edit-distance algorithm would refute SETH, a landmark transfer of SAT hardness to a natural sequence problem.[4]
2018
Authoritative summaryVassilevska Williams surveyed the fine-grained complexity program and the role of SETH and related hypotheses as bases for conditional lower bounds.[5]
2016
Peer reviewedCarmosino and collaborators formulated nondeterministic SETH variants and derived barriers to broad classes of deterministic fine-grained reductions, clarifying limitations of proof methods rather than…[6]

Mathematical neighborhood

Related results and reusable starting points

Current focusExponential Time Hypothesis and Strong Exponential Time Hypothesis

Stronger or generalized formStrong Exponential Time Hypothesis

SETH asserts that the limiting base-two exponent for k-SAT tends to one as the clause width grows. This implies ETH's positive-exponent assertion, while ETH alone does not imply the near-exhaustive-search exponent.

[1][3]

Logical consequenceP versus NP

Either ETH or SETH would imply P is not equal to NP. The known worst-case separation question P versus NP does not provide the quantitative exponential lower bounds asserted here.

[1][5]

Dependency or reductionSparsification Lemma

The sparsification lemma converts a k-CNF formula into a subexponential disjunction of formulas with linearly many clauses, allowing variable-based ETH lower bounds to transfer through reductions that control instance size.

[2]

Equivalent formulationHitting Set, Set Splitting, and NAE-SAT hypotheses

Under the paper's exact-exponential formulations and reductions, Hitting Set, Set Splitting, NAE-SAT, and related problems form an equivalence class with SETH. The encoding and parameter conventions are part of the equivalence.

[3]

Dependency or reductionStrongly subquadratic edit distance

A strongly subquadratic algorithm for edit distance would yield a faster SAT algorithm contradicting SETH, so SETH conditionally rules out such an edit-distance improvement.

[4]

Related problemNondeterministic Strong Exponential Time Hypothesis

NSETH and related nondeterministic hypotheses constrain which deterministic fine-grained reductions can establish lower bounds. They are separate assumptions, and their consequences are barriers to methods rather than counterexamples to SETH.

[6]

Related problemGap, counting, randomized, nonuniform, quantum, and parameterized ETH variants

Gap-ETH, #ETH, randomized ETH, nonuniform ETH, quantum SETH, and parameterized or pathwidth variants alter the problem, quantifiers, computational model, or parameter and must be tracked separately.

[5]

Related problemBounded-depth resolution over parities

The bounded-depth resolution-over-parities theorem establishes an analogue inside a restricted proof system. It is evidence about proof complexity, not a solution of the unrestricted algorithmic hypothesis.

[7]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

formal library support · partial resource linkedMathlib LRAT checker
Mathlib can check LRAT certificates for finite propositional unsatisfiability. This gives trusted support for individual CNF instances but does not formalize uniform algorithms, running-time functions, little-o exponents, or ETH and SETH themselves.
[10]
dataset · source linked; not reproduced by ProofAtlasSAT Competition 2026 benchmarks, solver sources, results, and certificates
The official competition publishes finite benchmark families, benchmark-selection scripts, solver source links, results, and certification requirements. These support reproducible finite SAT experiments but cannot decide an asymptotic lower-bound hypothesis.
[8]
software · source linked; not reproduced by ProofAtlasCaDiCaL SAT solver and proof interfaces
CaDiCaL is a maintained high-performance SAT solver with proof-production interfaces useful for concrete formulas. Solver success or failure on any finite suite is not evidence of an unconditional exponential lower bound.
[9]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetAn explicit uniform deterministic machine model, Boolean formula encoding, variable and input-size measures, and a formal worst-case running-time semantics.
Formalization targetFormal definitions of k-CNF satisfiability, optimal k-SAT exponents, subexponential time, and the limiting quantifiers distinguishing ETH from SETH.
Formalization targetA machine-checked sparsification lemma and size-preserving reduction framework capable of transporting quantitative exponential lower bounds.
Formalization targetA clear separation between the unrestricted algorithmic hypotheses and randomized, nonuniform, gap, counting, quantum, proof-system, or parameterized variants.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected supporting details in the research record. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

7 standing statements2 proposed statements3 open questions1 narrowed routes

Statements by mathematical role9 selected mapped statements

theorem candidate1 of 91
reduction3 of 93
lemma2 of 92
equivalence1 of 91
negative result1 of 91
computational claim1 of 91

Selected mathematical clusters3 mathematical clusters

Statements and reductionsClaims, implications, and derivations in the current map.17 displayed rows

retained route statement3-SAT needs exponential time; fixed-width SAT approaches the full base-two exponent as width grows.
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementSETH implies ETHintermediate
retained route statementNear-lossless Reed–Muller balance liftintermediate
retained route statementSharp balanced-SAT classificationintermediate
retained route statementParsimonious exact-regular hypergraph coreintermediate
retained route statementEdgewise two-state holographic rigidityintermediate
retained route statementFive- and six-frequency phase obstructionsintermediate
Recorded relationshipThe source material reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipthis work-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe current work reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed

Open questionsSpecific obligations that remain open in the current routes.3 displayed rows

Research targetDetermine the six-coordinate quadratic phase rank chi_2(6), including both six- and seven-phase cases.in progress reported
Research targetFind a subexponential collective evaluation of the correlated quadratic-sector family or equivalent unbounded phase decomposition.open
Research targetDetermine whether fixed-weight Pfaffian sectors collapse for the exact incidence signatures despite the universal all-weight barrier.open

Explored routes and evidenceChallenges, computations, and approaches that have already narrowed the search.3 displayed rows · 1 route included

Useful failureSource-reported limitationreported failure
ComputationExact finite certificates for unique-extension gadgets, hypergraph benchmarks, five- and six-frequency Fourier zero sets, and the five canonical rank-four dependence typesThe source reports a one-command suite and captured successful outputs, including exhaustive affine-orbit and phase-obstruction checks. Intake did not execute the supplied Python or C++ attachments, so the certificates are retained only as source-reported computational claims. · reported unreproduced
Narrowed routeSource-reported limitationWithin edge-dependent invertible two-by-two transformations that turn every exact-core NAE_3 and EQ_4 tensor into a standard matchgate signature, no new basis survives. The retained reductions and barriers do not prove a lower bound or supply a subexponential algorithm. A resolution still requires a genuinely subexponential algorithm for an ETH-equivalent core, a uniform base-saving algorithm for the direct SETH target, or an unrestricted complexity lower-bound breakthrough.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeDetermine the six-coordinate quadratic phase rank chi_2(6), including both six- and seven-phase cases.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointFind a subexponential collective evaluation of the correlated quadratic-sector family or equivalent unbounded phase decomposition.

Exponential Time Hypothesis and Strong ETH · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Must satisfiability require exponential time in the worst case, and does the best possible base for fixed-width SAT approach two as the clause width grows?

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references13 cited works · next context review by Nov 7, 2026

The mathematical context was checked on Aug 7, 2026. Status can be refreshed sooner after a material result or claim.

1
On the Complexity of k-SAToriginal source · Russell Impagliazzo, Ramamohan Paturi · Journal of Computer and System Sciences · 2001 · DOI 10.1006/jcss.2000.1727 · accessed Aug 7, 2026
2
Which Problems Have Strongly Exponential Complexity?original source · Russell Impagliazzo, Ramamohan Paturi, Francis Zane · Journal of Computer and System Sciences · 2001 · DOI 10.1006/jcss.2001.1774 · accessed Aug 7, 2026
3
On Problems as Hard as CNF-SATpeer reviewed result · Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström · ACM Transactions on Algorithms · 2016 · DOI 10.1145/2925416 · accessed Aug 7, 2026
4
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH Is False)peer reviewed result · Arturs Backurs, Piotr Indyk · SIAM Journal on Computing · 2018 · DOI 10.1137/15M1053128 · accessed Aug 7, 2026
5
Fine-grained Algorithms and Complexitysurvey or monograph · Virginia Vassilevska Williams · Leibniz International Proceedings in Informatics · 2018 · DOI 10.4230/LIPIcs.ICDT.2018.1 · accessed Aug 7, 2026
6
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibilitypeer reviewed result · Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider · Innovations in Theoretical Computer Science · 2016 · DOI 10.1145/2840728.2840746 · accessed Aug 7, 2026
7
Strong ETH Holds for Bounded-Depth Resolution over Paritiespeer reviewed result · Klim Efremenko, Dmitry Itsykson · ACM Symposium on Theory of Computing · 2026 · DOI 10.1145/3798129.3800804 · accessed Aug 7, 2026
8
SAT Competition 2026software or dataset · SAT Competition organizers · accessed Aug 7, 2026
9
CaDiCaL SAT solversoftware or dataset · Armin Biere, CaDiCaL contributors · GitHub · accessed Aug 7, 2026
10
Mathlib: checking LRAT unsatisfiability certificatesformalization · Mathlib contributors · Lean community · accessed Aug 7, 2026
11
Exponential time hypothesisencyclopedia · Wikimedia Foundation · accessed Aug 7, 2026
12
List of unsolved problems in computer scienceencyclopedia · Wikimedia Foundation · accessed Aug 7, 2026
13
Formal Conjectures repositoryformalization · Google DeepMind · GitHub · accessed Aug 7, 2026

Important qualifications

The target uses deterministic, uniform, worst-case SAT formulations. Randomized, nonuniform, counting, gap, quantum, proof-complexity, and parameterized or pathwidth variants are not merged into ETH or SETH.
SETH is strictly stronger as a conjectural assertion than ETH: SETH implies ETH, while ETH does not assert that the limiting k-SAT exponent equals one.
The structured proposed year is the 2001 peer-reviewed publication year. An earlier 1999 conference version introduced the k-SAT exponent framework and remains in the current research map in the historical summary rather than assigned a second identity year.
Conditional lower bounds and equivalence reductions are consequences under ETH or SETH, not evidence that proves either hypothesis.
The 2026 theorem Strong ETH Holds for Bounded-Depth Resolution over Parities concerns restricted proof systems. Its title must not be read as a proof of the algorithmic Strong Exponential Time Hypothesis.
SAT Competition results, solver performance, and finite LRAT certificates establish facts about concrete formulas only; they cannot prove a universal asymptotic time lower bound.
The scoped formalization search found finite SAT-certificate infrastructure but no statement-aligned formalization of ETH or SETH with all machine-model, encoding, uniformity, and asymptotic conventions. This does not prove absence from every formal library.
Wikipedia references are quiet context only, and no prize-level or selective maintained-list distinction was verified. The fine-grained reduction literature is represented rather than exhaustively enumerated.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces