In computational complexity theory, the exponential time hypothesis or ETH is an unproven computational hardness assumption that was formulated by Impagliazzo & Paturi (1999). It states that satisfiability of 3-CNF Boolean formulas (3-SAT) cannot be solved in subexponential time, ${\displaystyle 2^{o(n)}}$. More precisely, the usual form of the hypothesis asserts the existence of a number ${\displaystyle s_{3}>0}$ such that all algorithms that correctly solve 3-SAT require time at least ${\displaystyle 2^{s_{3}n}.}$ The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. Beyond NP-complete problems, it implies that many known algorithms (including those with lower than exponential time) have optimal or near-optimal time complexity.

The ${\displaystyle k}$-SAT problem is a version of the Boolean satisfiability problem in which the input to the problem is a Boolean expression in conjunctive normal form (that is, an and of ors of variables and their negations) with at most ${\displaystyle k}$ variables per clause. The goal is to determine whether this expression can be made to be true by some assignment of Boolean values to its variables. 2-SAT has a linear time algorithm, but all known algorithms for larger ${\displaystyle k}$ take exponential time, with the base of the exponential function depending on ${\displaystyle k}$. For instance, the WalkSAT probabilistic algorithm can solve ${\displaystyle k}$-SAT in average time $${\displaystyle \left(2-{\frac {2}{k}}\right)^{n}n^{O(1)},}$$ where ${\displaystyle n}$ is the number of variables in the given ${\displaystyle k}$-SAT instance. For each integer ${\displaystyle k\geq 3}$, define ${\displaystyle s_{k}}$ to be the smallest number such that ${\displaystyle k}$-SAT can be solved in time ${\displaystyle 2^{s_{k}n+o(n)}}$. This minimum might not exist, if a sequence of better and better algorithms have correspondingly smaller exponential growth in their time bounds; in that case, define ${\displaystyle s_{k}}$ to be the infimum of the real numbers ${\displaystyle \delta }$ for which ${\displaystyle k}$-SAT can be solved in time ${\displaystyle O(2^{\delta n})}$. Because problems with larger ${\displaystyle k}$ cannot be easier, these numbers are ordered as ${\displaystyle s_{3}\leq s_{4}\leq \cdots }$, and because of WalkSAT they are at most $${\displaystyle s_{k}\leq \log _{2}\left(2-{\frac {2}{k}}\right)<1.}$$ The exponential time hypothesis is the conjecture that they are all nonzero, or equivalently, that the smallest of them, ${\displaystyle s_{3}}$, is nonzero.

Some sources define the exponential time hypothesis to be the slightly weaker statement that 3-SAT cannot be solved in time ${\displaystyle 2^{o(n)}}$. If there existed an algorithm to solve 3-SAT in time ${\displaystyle 2^{o(n)}}$, then ${\displaystyle s_{3}}$ would equal zero. However, it is consistent with current knowledge that there could be a sequence of 3-SAT algorithms, each with running time ${\displaystyle O(2^{\delta _{i}n})}$ for a sequence of numbers ${\displaystyle \delta _{i}}$ tending towards zero, but where the descriptions of these algorithms are so quickly growing that a single algorithm could not automatically select and run the most appropriate one. If this were to be the case, then ${\displaystyle s_{3}}$ would equal zero even though there would be no single algorithm running in time ${\displaystyle 2^{o(n)}}$. A related variant of the exponential time hypothesis is the non-uniform exponential time hypothesis, which posits that there is no family of algorithms (one for each length of the input, in the spirit of advice) that can solve 3-SAT in time ${\displaystyle 2^{o(n)}}$.

Because the numbers ${\displaystyle s_{3},s_{4},\dots }$ form a monotonic sequence that is bounded above by one, they must converge to a limit $${\displaystyle s_{\infty }=\lim _{k\to \infty }s_{k}.}$$ The strong exponential time hypothesis (SETH) is the conjecture that ${\displaystyle s_{\infty }=1}$.

It is not possible for ${\displaystyle s_{k}}$ to equal ${\displaystyle s_{\infty }}$ for any finite ${\displaystyle k}$: as Impagliazzo, Paturi & Zane (2001) showed, there exists a constant ${\displaystyle \alpha }$ such that ${\displaystyle s_{k}\leq s_{\infty }(1-\alpha /k)}$. Therefore, if the exponential time hypothesis is true, there must be infinitely many values of ${\displaystyle k}$ for which ${\displaystyle s_{k}}$ differs from ${\displaystyle s_{k+1}}$.

An important tool in this area is the sparsification lemma of Impagliazzo, Paturi & Zane (2001), which shows that, for every ${\displaystyle \varepsilon >0}$, any ${\displaystyle k}$-CNF formula can be replaced by ${\displaystyle O(2^{\varepsilon n})}$ simpler ${\displaystyle k}$-CNF formulas in which each variable appears only a constant number of times, and therefore in which the number of clauses is linear. The sparsification lemma is proven by repeatedly finding large sets of clauses that have a nonempty common intersection in a given formula, and replacing the formula by two simpler formulas, one of which has each of these clauses replaced by their common intersection and the other of which has the intersection removed from each clause. By applying the sparsification lemma and then using new variables to split the clauses, one may then obtain a set of ${\displaystyle O(2^{\varepsilon n})}$ 3-CNF formulas, each with a linear number of variables, such that the original ${\displaystyle k}$-CNF formula is satisfiable if and only if at least one of these 3-CNF formulas is satisfiable. Therefore, if 3-SAT could be solved in subexponential time, one could use this reduction to solve ${\displaystyle k}$-SAT in subexponential time as well. Equivalently, if ${\displaystyle s_{k}>0}$ for any ${\displaystyle k>0}$, then ${\displaystyle s_{3}>0}$ as well, and the exponential time hypothesis would be true.

The limiting value ${\displaystyle s_{\infty }}$ of the sequence of numbers ${\displaystyle s_{k}}$ is at most equal to ${\displaystyle s_{\operatorname {CNF} }}$, where ${\displaystyle s_{\operatorname {CNF} }}$ is the infimum of the numbers ${\displaystyle \delta }$ such that satisfiability of conjunctive normal form formulas without clause length limits can be solved in time ${\displaystyle O(2^{\delta n})}$. Therefore, if the strong exponential time hypothesis is true, then there would be no algorithm for general CNF satisfiability that is significantly faster than a brute-force search over all possible truth assignments. However, if the strong exponential time hypothesis fails, it would still be possible for ${\displaystyle s_{\operatorname {CNF} }}$ to equal one.

The exponential time hypothesis implies that many other problems in the complexity class SNP do not have algorithms whose running time is faster than ${\displaystyle c^{n}}$ for some constant ${\displaystyle c}$. These problems include graph k-colorability, finding Hamiltonian cycles, maximum cliques, maximum independent sets, and vertex cover on ${\displaystyle n}$-vertex graphs. Conversely, if any of these problems has a subexponential algorithm, then the exponential time hypothesis could be shown to be false.