The Strong Exponential Time Hypothesis (SETH) is a conjecture in computational complexity about the time required to solve the Boolean satisfiability problem. It states that, for every constant , there is a fixed clause width for which -SAT cannot be solved by a deterministic algorithm in time , apart from factors polynomial in the input size, where is the number of Boolean variables. Informally, algorithms for increasingly wide clauses cannot maintain a fixed improvement over the exponent of exhaustive search. SETH is unproved and serves as a foundation for many conditional running-time lower bounds.
Formal statement
A Boolean formula in conjunctive normal form is an AND of clauses, each of which is an OR of literals. A literal is a variable or its negation. In -SAT, each clause contains at most literals, and the task is to determine whether some assignment of truth values satisfies every clause.
Trying all assignments gives a running time of , where is the input length. The notation suppresses polynomial factors in that length.
One formulation defines
Since allowing wider clauses includes all instances with narrower clauses, is nondecreasing in , and exhaustive search gives . SETH asserts
Equivalently, for every , some fixed admits no deterministic -time algorithm.
Why the quantifier order matters
SETH does not assert that every fixed-width satisfiability problem requires time. For each fixed , algorithms can achieve an exponential base strictly below . SETH allows those improvements, provided their advantage can vanish as increases.
For example, a hypothetical family of algorithms with running times
would be consistent with SETH: the improvement in the exponent approaches zero.
By contrast, algorithms running in for every fixed would refute SETH. The algorithms could differ with ; what matters is that the improvement would be independent of clause width.
The parameter is the number of variables, not the number of clauses or the total encoding length. This distinction is important when interpreting reductions and lower bounds.
Origins and relation to ETH
SETH emerged from work by Russell Impagliazzo and Ramamohan Paturi on the exponential-time complexity of satisfiability, notably their 2001 paper On the Complexity of k-SAT. It strengthens the Exponential Time Hypothesis (ETH).
In the notation above, ETH asserts that
Thus, ETH postulates a positive exponential rate for solving 3-SAT, whereas SETH asserts that the rates for -SAT approach as clause width grows.
The distinction is substantial. ETH could remain true even if every fixed-width satisfiability problem were solvable in time. Such a uniform improvement would contradict SETH.
SETH implies ETH. A key ingredient connecting the two is the sparsification lemma, which decomposes a fixed-width formula into a controlled number of sparse formulas. It enables reductions to preserve sufficiently precise exponential running-time bounds.
Both hypotheses imply that P differs from NP, but neither follows merely from that separation. The assertion that no polynomial-time algorithm exists says much less than a conjecture specifying an exponential rate. Likewise, NP-completeness alone does not establish a SETH-style running-time lower bound.
Role in fine-grained complexity
SETH is a central assumption in fine-grained complexity, which studies the precise running times of computational problems, including problems already known to be solvable in polynomial time.
A conventional polynomial-time reduction may establish that a problem is NP-hard, but it usually does not preserve running times precisely enough to distinguish, for example, quadratic from strongly subquadratic algorithms. A fine-grained reduction instead tracks how an improvement in one problem would produce a forbidden improvement in another.
A typical SETH-based result has the form:
If problem has an -time algorithm for some fixed , then SETH is false.
Such a statement conditionally rules out strongly subquadratic algorithms. It does not necessarily exclude running times such as
because neither has the form for a fixed positive .
The conclusion is conditional rather than an unconditional lower bound: either the proposed fast algorithm does not exist, or SETH fails.
A representative reduction: orthogonal vectors
The orthogonal vectors problem illustrates how satisfiability hardness can translate into a quadratic-time barrier.
In its bichromatic Boolean form, the input consists of two sets , each containing vectors. The question is whether there are vectors and with
Because the coordinates are nonnegative, orthogonality means that no coordinate contains a in both vectors.
A basic reduction from satisfiability proceeds as follows:
- Divide the formula’s variables into two approximately equal groups.
- Enumerate all assignments to each group.
- Give each partial assignment a vector with one coordinate per clause.
- Set a coordinate to exactly when that partial assignment satisfies no literal in the corresponding clause.
Two partial assignments combine into a satisfying assignment precisely when their vectors are orthogonal. Every clause must be satisfied by at least one half.
Each vector set has size approximately
For fixed , the formula can be normalized to have only polynomially many distinct clauses, so . An algorithm with running time
would therefore yield a satisfiability algorithm running in
If this improvement applied uniformly to every fixed clause width, it would contradict SETH.
Using sparsification, standard formulations obtain conditional quadratic barriers even for dimensions proportional to , with the proportionality constant depending on the desired exponent improvement. The dimension restriction is essential: low-dimensional special cases can have faster algorithms without contradicting SETH.
Applications to sequence problems
SETH-based reductions support lower bounds for several classical sequence problems.
For edit distance, standard dynamic programming computes the distance between two length- strings in quadratic time. SETH implies that exact edit distance, even over suitable fixed finite alphabets, has no -time algorithm for any constant .
Comparable strongly subquadratic barriers are known for longest common subsequence under standard formulations. These results are notable because the problems are polynomial-time solvable: the conjectured difficulty concerns improving the polynomial exponent, not deciding whether polynomial-time algorithms exist.
Such lower bounds depend on the exact problem definition. Exact computation, approximation, restricted alphabets, bounded distance, and compressed inputs are different settings. A lower bound for one does not automatically apply to the others.
Variants and scope
Deterministic and randomized algorithms
The usual deterministic formulation of SETH excludes deterministic satisfiability algorithms with the specified running times. The randomized Strong Exponential Time Hypothesis, often called randomized SETH, makes the corresponding assertion for bounded-error randomized algorithms.
This distinction matters when a proposed target algorithm is randomized: combining it with a deterministic reduction generally produces a randomized satisfiability algorithm. A lower-bound claim must therefore specify the appropriate assumption.
Decision and counting
SETH concerns deciding whether a satisfying assignment exists. Counting satisfying assignments is a different problem, and counting versions of exponential-time hypotheses are separate assumptions. A decision-based lower bound should not be silently replaced by a counting-based one.
Classical and quantum computation
SETH is normally an assumption about classical computation. A quantum computer can use Grover’s algorithm to search the assignment space in roughly oracle queries, with polynomial overhead for evaluating a formula. This does not refute classical SETH. Quantum lower-bound research requires assumptions formulated for quantum algorithms.
Limitations and interpretation
SETH is a worst-case hypothesis. It does not imply that typical satisfiability instances, application-specific instances, or experimentally generated instances require exhaustive-search-like running times. Practical solvers can exploit structure and heuristics that are not reflected in worst-case bounds.
Nor does SETH exclude every useful improvement. Faster polynomial factors, smaller memory requirements, special-case algorithms, and approximation algorithms may remain possible. The precise restriction depends on the reduction and on whether it preserves input size, parameters, randomness, and the required output.
Finally, SETH is stronger than what many individual lower-bound arguments need. A theorem proved assuming SETH may also follow from a weaker, problem-specific conjecture. Conversely, refuting SETH would invalidate SETH as a justification for its consequences, but would not automatically supply fast algorithms for every problem whose known lower bound relies on it: a reduction transfers an algorithmic improvement only in its established direction.