What the Exponential Time Hypothesis Says About Hard Problems

What is the Exponential Time Hypothesis?

The Exponential Time Hypothesis, usually shortened to ETH, is an unproven claim about how difficult certain computer problems are. In its usual form, it says that 3-SAT cannot be solved in subexponential time. In plain language, it predicts that solving these problems will, in the worst case, take a very long time as the problem grows. ⁴

An hypothesis in this setting is an assumption researchers use to reason about algorithms. It is not a result that has been proved. ETH was formulated by Impagliazzo and Paturi in 1999, according to the reference source. ⁴

What is 3-SAT?

3-SAT is a version of the Boolean satisfiability problem. A Boolean variable has one of two values: true or false. The problem is to decide whether there is some assignment of values that makes a formula true. In 3-SAT, the formula is in a form made up of clauses with three variables. ⁴

The question sounds simple, but the number of possible assignments can grow rapidly as more variables are added. ETH makes a stronger claim than saying that no quick method is currently known: it says that no algorithm can solve all such instances in subexponential time. ⁴

What does “subexponential time” mean?

It describes an algorithm whose running time grows more slowly than an exponential-time approach as the problem size increases. The supplied reference gives the central claim in those terms, but does not provide a fuller technical definition. ⁴

The important point for a general reader is that ETH is about how running time scales as a problem gets larger, not about how long one particular computer takes on one particular task. It is a statement about the limits of algorithms in the worst case. ⁴

Why does ETH matter to computer science?

ETH matters because it gives researchers a way to reason about whether an algorithm might be improved substantially. If ETH is true, it implies that P is not equal to NP, a major open question about whether problems whose answers can be checked efficiently can also be solved efficiently. ⁴

The hypothesis also has consequences beyond 3-SAT. The reference source says it implies that many known algorithms have optimal or near-optimal running times. That makes ETH useful as a benchmark: researchers can ask not only whether an algorithm works, but whether its speed is likely to be close to the best possible. ⁴

That does not mean ETH tells us the exact runtime for every real-world task. It is a theoretical assumption about a class of problems. Its usefulness depends on whether the assumption is true and on how it applies to the specific problem being studied.

Has ETH been disproved?

Recent reports describe OpenAI as claiming that its AI work disproved ETH. One report also says the company involved outside experts, described as “shepherds,” in guiding results in computer science and physics. ¹²

The supplied reports do not include the proof, its technical details, or an independent assessment of whether it establishes the claim. One of the reports presents the ETH discussion in a joking tone and says the author is paraphrasing a video, so it is not enough on its own to verify a breakthrough. ² The other reports a broad claim but does not provide the evidence needed to evaluate it. ¹

For that reason, the careful answer is that ETH remains described in the reference material as unproven, while a recent claim of disproof has been reported but cannot be judged from the available details. ¹²⁴ A proof would need to be examined by experts in the relevant area before readers could know what it establishes.

What does ETH mean for people outside research?

ETH does not tell an ordinary computer user that a particular app or device will be slow. It is a tool for theoretical computer science, where researchers study what algorithms can do as problems grow. Its practical value is indirect: it can help set expectations about whether a much faster general method is plausible for certain hard problems. ⁴

The main takeaway is that ETH is a powerful but unproven assumption. It helps researchers reason about hard problems, but it should not be treated as a settled fact or as proof that every difficult computing task is impossible to speed up.