A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Exponential Time Hypothesis (ETH), proposed by Impagliazzo and Paturi, conjectures that k-SAT requires 2^(Omega(n)) time. The Strong Exponential Time Hypothesis (SETH) strengthens this: there is no sequence of algorithms (one per k) such that k-SAT is solvable in 2^((1 - epsilon_k) k n) time for all k, where epsilon_k approaches 0. Equivalently, for infinitely many k, every k-SAT solver requires 2^((1 - o(1)) k n) time. These hypotheses are widely believed but unproven, sitting between P != NP and the strong claim that exponential time is fundamentally necessary. ETH and SETH enable conditional hardness: assuming the hypothesis, one can prove lower bounds on the running time of other problems by reduction, explaining why decades of algorithmic research have not substantially improved brute-force algorithms for many classical problems (3-SUM, Longest Common Subsequence, all-pairs shortest paths).
The Exponential Time Hypothesis is a precision sharpening of P != NP. While P != NP merely says that k-SAT cannot be solved in polynomial time, ETH and SETH make specific quantitative claims: the running time must be exponential in n, and moreover, the exponential base grows with k (for SETH). These hypotheses are not proven, but they are widely believed based on decades of algorithmic research: all known SAT solvers, despite substantial engineering, have exponential worst-case complexity.
ETH states that there is no 2^(o(n)) algorithm for 3-SAT — in other words, you cannot beat 2cn for any arbitrarily small constant c > 0. This is weaker than claiming 2n is necessary (you could have 20.5 n), but it rules out subexponential-time solutions. SETH goes further: it asserts that for each k, the exponent in the 2e * k * n running time cannot be reduced — the dependence on k is fundamental. SETH is equivalent to: for every epsilon > 0, there exists k such that k-SAT requires 2^((1 - epsilon) * k * n) time.
The power of ETH and SETH lies in their use as anchors for conditional lower bounds. Suppose you want to prove that problem X cannot be solved faster than O(n2). A direct lower bound (e.g., information-theoretic) might be infeasible. Instead, construct a fine-grained reduction: a algorithm that, given an O(n1.99) solver for X, constructs an O(20.99 n) solver for 3-SAT, contradicting ETH. Thus, under ETH, X requires Omega(n2) time. This conditional approach has been devastatingly effective: 3-SUM, Longest Common Subsequence, Edit Distance, All-Pairs Shortest Paths, and hundreds of other natural problems are now known to be hard under SETH or 3-SUM conjecture.
The reductions use many techniques: hardness amplification (taking a single hard instance and repeating it with independence), gadget construction (replacing variables with subproblems), and composition. A successful reduction is surprising: it shows that two seemingly unrelated problems (SAT and substring matching, for instance) are algorithmically equivalent at the exponential level, tied together by the underlying hardness assumptions. The fine-grained complexity landscape reveals that the difficulty of computational problems is not binary (polynomial vs. exponential) but stratified: different problems cluster around different hardness anchors (SETH, 3-SUM, Orthogonal Vectors), explaining why some problems resist faster algorithms despite intense effort while others yield to clever algorithms.
The status of SETH remains open, but the conditional hardness web it enables is robust and reveals deep structure in computational difficulty.