Strong Exponential Time Hypothesis

A set of switches must satisfy several rules. Each rule allows a choice, such as “x is on, or y is on, or z is on”; all rules must hold together. Add “x is off, or y is on, or z is on.” The setting x on, y off, z off fails the second rule, while x on, y on, z off satisfies both. Three switches have eight settings to test, and each extra switch doubles that number. The hypothesis says that algorithms without random choices have no fixed improvement to this exponential growth rate that works for every fixed limit on rule length.[3] [4]

Boolean satisfiability asks whether some on/off setting makes every clause in a formula true. Can algorithms beat exhaustive search by one common fixed improvement in the exponential base across all fixed clause widths? A literal is a switch or its negation; a clause is an OR of literals, and the formula is an AND of clauses. For example, $(x\lor y\lor z)\land(\neg x\lor y\lor z)$ is satisfied by six of its eight settings: it is equivalent to requiring at least one of $y,z$ to be on. This is an illustrative easy instance, not a hardness witness.

There are $2^n$ settings for $n$ variables. In $k$-SAT every clause has at most $k$ literals. SETH asserts that for every fixed $0<\varepsilon<1$, some fixed $k$ admits no deterministic algorithm with running time $O((2-\varepsilon)^n\operatorname{poly}(m))$, where $m$ is encoded input length. The width may depend on the proposed saving $\varepsilon$, but is fixed as $n$ grows. Negating the hypothesis would give a shared base improvement for all fixed widths, while allowing the algorithms and polynomial factors to depend on the width.[3] [4]

The hypothesis is unproved. Faster algorithms for short rules can coexist with it. For each proposed fixed improvement, it predicts that some fixed larger rule length defeats that guarantee. Different rule lengths may have different algorithms; what is ruled out is a shared improvement in their exponential growth rate.[3]

Neither this hypothesis nor its negation is established. Improvements for a particular width, useful heuristics or typical inputs leave the worst-case quantifiers intact. ETH excludes subexponential algorithms for a fixed small width and is weaker than SETH. The June 2026 furthest-pair preprint assumes SETH or an orthogonal-vectors hypothesis; its reductions do not establish either assumption. Claims about randomized or quantum algorithms require their own model-specific hypotheses.[2] [3] [4]

Many difficult tasks can encode these switch rules. A sufficiently fast solver for one of those tasks would then also solve the rules faster. This gives conditional barriers rather than proofs of impossibility: for example, a 2026 result connects the hypothesis to finding the furthest pair of points when the number of coordinates grows with the input.[2] [3]

Among $N$ points there are $N(N-1)/2$ candidate pairs. The June 2026 preprint reports that, under SETH, exact furthest pair has no running-time bound $O(N^{2-\delta})$ for any fixed $\delta>0$ when dimension is efficiently constructible and grows without bound with $N$. The dimension condition matters: it is not a barrier for points in a fixed plane. Such reductions explain why improving the power of a geometric algorithm could require a corresponding breakthrough in Boolean search, while leaving approximation and restricted inputs as separate questions.[2] [3]