Exponential Time Hypothesis

Some computational problems seem to always take a very long time, no matter how cleverly one approaches them. The Exponential Time Hypothesis, ETH for short, is a conjecture from theoretical computer science — the subfield that studies what computers can fundamentally achieve and what they cannot. It claims: for a certain class of problems, there is no algorithm that is substantially faster than exponential. An algorithm running in exponential time doubles its running time when the problem is enlarged by just a single step. With twenty variables, it already needs more than a million steps; with sixty variables, even the fastest supercomputer would be overwhelmed. The ETH says: at its core, nothing can be done to change this.

The ETH as a Benchmark for Algorithms

Without the ETH, one could still hope: perhaps someone will discover a brilliant trick tomorrow that suddenly makes a hard problem quickly solvable. The ETH systematically limits this hope. It provides a theoretical foundation on which computer scientists can prove: if the ETH is true, then no algorithm for problem X can be faster than Y.

This is practically important because it saves research time. Anyone who knows that a faster solution would be impossible under the ETH does not need to keep searching. Instead, one can specifically look for good approximate solutions that do not solve the problem perfectly, but fast enough. The ETH thus shifts the focus from “Is there a perfect solution?” to “What is the best we can realistically achieve?”

It is important to note: the ETH has not been proven to this day. It is a conjecture, albeit one that nearly all experts believe. Many results in algorithmics depend on it — similar to a house of cards that stands stably as long as the bottom card holds.

The Core Problem Behind the Hypothesis

The ETH originally refers to a specific problem called SAT — short for the satisfiability problem. This concerns logical statements with many variables that can be either true or false. The question is: is there an assignment of the variables that satisfies the entire statement? One can imagine this as a giant puzzle where one has to flip many switches to make a lamp light up — and there is no scheme that tells you in which order to begin.

The ETH claims: for SAT, every algorithm requires, in the worst case, time that grows exponentially with the number of variables. A stronger variant, the Strong Exponential Time Hypothesis (SETH), tightens this further. It states that not even slight improvements to the exponential running time are possible. From SETH, even tighter bounds can be derived for many other problems.

The crucial line of reasoning behind this is as follows: if one can show that a problem is at least as hard as SAT, then the same limits apply to that problem. This transferring of difficulty is called reduction — a central tool in theoretical computer science.

Where the ETH Appears in Practice

The ETH appears wherever computer scientists want to justify why a problem is and remains hard. In database research, for instance, ETH-based arguments are used to show that certain queries over large amounts of data cannot be answered substantially faster than current systems already do. In network analysis, it justifies why certain optimization problems on large graphs — structures made of points and connections — cannot be solved efficiently.

It also plays a role in AI research. Many planning and search problems that AI systems are meant to solve are closely related to SAT. The ETH helps set realistic expectations: not every problem that a human can intuitively solve can also be efficiently automated.

In the news, the ETH rarely appears directly — more often it lurks behind headlines such as “Quantum computer solves problem that classical computers cannot.” Such claims can only be properly assessed once one knows what the ETH says about the limits of classical algorithms. It is thus less an everyday term than a key concept that, in the background, structures many discussions about computing power and AI capabilities.