Exponential Time Hypothesis

A conjecture in computational complexity theory stating that k-SAT problems such as 3-SAT cannot be solved in subexponential time.

1 articleLast mentioned

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).

This entry is based on AIPOST articles and widely known facts. If something is wrong, please send us a correction request.

Articles covering this entry

  • ETH Disproof by OpenAI's AI: What Changes for P vs NP and CryptographyAI News ·

    …ober 26, 2026 that one of its AI models produced a proof that the Exponential Time Hypothesis (ETH), a conjecture that computer scientists have treated as a bed…

    Read article

Found a mistake or missing an entry?

Wiki entries are based on AIPOST articles and widely known facts. If an entry is wrong, send us a correction request and we will check and fix it. Names from new articles are added to the wiki after the article is published.