The Exponential Time Hypothesis (ETH) is a conjecture in computational complexity theory asserting that 3-SAT on n variables cannot be solved in subexponential time, that is, in time 2^{o(n)}. It was proposed in the late 1990s by Russell Impagliazzo and Ramamohan Paturi in their work on the complexity of k-SAT, and a follow-up paper with Francis Zane introduced the sparsification lemma that allows the hypothesis to be transferred to many other problems.
ETH is a stronger assumption than P ≠NP: whereas P ≠NP only rules out polynomial-time algorithms for NP-complete problems, ETH rules out any algorithm meaningfully faster than exponential time. It has served as the basis for conditional lower bounds in graph algorithms, parameterized complexity, and fine-grained complexity. The stronger conjecture that 3-SAT cannot be solved in time 2^{(1-ε)n} is known as the Strong Exponential Time Hypothesis (SETH).