Definition
Exponential Time Hypothesis is the Exponential Time Hypothesis (ETH) is a conjecture in computer science that the logic puzzle 3-SAT cannot be solved in subexponential time, meaning no algorithm is much faster than trying nearly every possibility.
The Exponential Time Hypothesis, or ETH, is a famous unproven claim about how hard one particular puzzle is. It was proposed by Russell Impagliazzo and Ramamohan Paturi, and a large body of theory has been built on the assumption that it is true.
3-SAT asks whether a logical formula can be made true. The formula is a list of rules, each involving three yes-or-no variables, such as "A or not B or C." You must find settings for all the variables that satisfy every rule at once, or prove none exist.
Checking a proposed answer is easy. Finding one is hard. With n variables there are 2^n possible settings, and the best known methods for decades have stayed in the exponential range: adding one more variable multiplies the work.
ETH says this wall is real. Informally, no algorithm can solve 3-SAT in time that grows more slowly than exponentially in the number of variables. In math notation, it rules out running times of the form 2^o(n), where the o means "grows slower than n."
It is a stronger claim than P versus NP. P versus NP asks only whether a fast, polynomial-time method exists. ETH says that even the slower, subexponential methods do not exist. If ETH is true, then P does not equal NP, but the reverse is not guaranteed.
Researchers use ETH as a yardstick. If solving some other problem quickly would also let you solve 3-SAT quickly, then a fast algorithm for that problem would break ETH. This lets theorists show that many problems, in scheduling, routing and graph analysis, probably cannot be solved much faster than the best known methods, without proving anything absolute.
Most software engineers never touch ETH directly. Real SAT solvers handle huge practical formulas well because real formulas are not the worst case. A theoretical result about the worst case, even a surprising one, does not by itself make those tools faster. A result that was purely asymptotic could matter for the theory long before it changes any code.
ETH is part of the study of computational complexity. Proofs in this area are increasingly checked by software, using systems such as Lean, which matters when a surprising claim needs to be trusted. For the broader idea of formal proof, see formal verification.
Is ETH proven? No. It is a hypothesis, which is why it is useful as an assumption. Is it the same as P versus NP? No. It is a stronger statement about how long 3-SAT takes.
No. It is an unproven conjecture that researchers use as an assumption to show other problems are probably hard.
P versus NP asks whether any polynomial-time method exists for hard problems. ETH is stronger: it says 3-SAT has no subexponential-time algorithm at all.
OpenAI posted a paper on Oct. 26 saying its model refuted the Exponential Time Hypothesis, and Anthropic posted a Claude-found refutation hours later, both checked in Lean. Take the claim seriously and the speedup lightly.