Exponential time hypothesis (ETH)

Some problems can only be solved by trying out nearly every possibility. The exponential time hypothesis, ETH for short, is computer scientists’ bet that for one particular problem there is no way round this, however clever we are. Faster methods do exist, but even the best of them will need a number of steps that grows exponentially with the size of the problem.

ETH is closely tied to the P versus NP problem, which has an article of its own. If you haven’t read it, have a look there first, because we’ll be building on it, above all on what the complexity of an algorithm is and why there is such a gulf between n² and 2ⁿ.

Who to invite to the party

You’re planning a party and want to invite four friends: Tom, Jack, Kate and Dan. The catch is that they don’t all get on, and you’d like everyone to be happy. After a lot of asking around, you end up with six conditions:

Tom comes, or Kate does (or both).
Jack and Kate can’t stand each other, so they won’t both come.
Dan only comes if Jack comes too.
If Tom comes, then Kate or Dan has to come as well.
If Tom and Kate both come, Jack has to come too.
At least one of Tom, Jack and Dan comes.

Who should you invite so that all the conditions hold at once? Try to work it out yourself; the solution is tucked away at the end of the article.

A computer scientist would rewrite the problem in the language of propositional logic. Each friend gets a letter, say T for Tom. The letter is either true (Tom comes) or false (Tom doesn’t come). The symbol ∨ is read “or” and ¬ is read “not”. The first condition then looks like this:

$T \lor K$

The second condition says that Jack doesn’t come or Kate doesn’t come:

$\neg J \lor \neg K$

The third condition is easy to get wrong. “Dan only comes if Jack comes too” means that it must not happen that Dan comes and Jack doesn’t. So either Dan doesn’t come, or Jack does:

$\neg D \lor J$

We rewrite the rest in the same way. The whole problem then looks like this:

$\begin{array}{rcl} 1. & T \lor K \\ 2. & \neg J \lor \neg K \\ 3. & \neg D \lor J \\ 4. & \neg T \lor K \lor D \\ 5. & \neg T \lor \neg K \lor J \\ 6. & T \lor J \lor D \end{array}$

Look how alike the conditions are: a few letters, some with the ¬ sign, joined by the word “or”. And none of them has more than three letters. A problem where we have conditions like these and we’re looking for a way to assign true and false to the letters so that all of them hold at once is called 3-SAT. The three means a condition has at most three letters, and SAT is short for satisfiability.

At first glance it looks like a puzzle from the back pages of a magazine. But a huge number of practical problems can be rewritten as 3-SAT: school timetables, checking that a processor chip calculates correctly, planning work shifts and even sudoku. Then there aren’t four letters but easily millions.

How many possibilities do we have to try?

The most straightforward approach is to try everything. Tom comes or he doesn’t, which gives two possibilities. For each of them Jack comes or doesn’t, which already makes four. For four friends there are

$2 \cdot 2 \cdot 2 \cdot 2 = 2^{4} = 16.$

We used the same reasoning for binary vectors in the article on P vs. NP. If we have n letters, we can assign true and false to them in 2ⁿ ways. For 4 friends that’s 16 possibilities, which you can get through in a few minutes. For 100 letters it’s

$2^{100} \approx 1.27 \cdot 10^{30}$

possibilities. If a computer tried a billion possibilities a second, it would need roughly three thousand times as long as the universe has existed.

The other way round, though, it’s easy: if someone tells you “invite these three”, you can check it straight away. You just go through the six conditions and see whether each one holds. Finding a solution is hard; checking it is easy. These are exactly the problems that we put in the class NP in the article on P vs. NP.

And 3-SAT isn’t just any problem in NP: in 1971 it was shown that every problem in NP can be translated into 3-SAT. So anyone who could solve 3-SAT quickly could quickly solve absolutely everything that can be checked quickly. Problems with this property are called NP-complete, and 3-SAT is the most famous of them.

Can we do better than 2ⁿ?

We can. Trying absolutely everything is wasteful. For example, once we notice that Tom isn’t coming, the first condition tells us immediately that Kate has to come. We can rule out at once all the possibilities where neither of them comes. Clever algorithms combine a whole range of tricks like this. The best ones known today need roughly

${1.307}^{n}$

steps. That’s a huge leap. For n = 100 we get roughly 4.2 · 10¹¹ steps instead of 10³⁰, which a computer can manage in a few minutes.

But watch out, there’s a catch. 1.307ⁿ is still an exponential function. We’ve shrunk the base from two to 1.307, but the variable n is still in the exponent. As n keeps growing, it will flatten us in the end anyway. For n = 1000 even 1.307ⁿ is a number with 117 digits.

So what would a non-exponential algorithm look like? One that gets by with n³ steps, for example. It would be polynomial, and 3-SAT would then belong to the class P. Between polynomials and exponentials, though, there is a grey zone: functions that grow faster than every polynomial and yet more slowly than every exponential. For example

$2^{\sqrt{n}} .$

Here only the square root of n is in the exponent. Let’s compare all four functions in a table:

n	n³	$2^{\sqrt{n}}$	1.307ⁿ	2ⁿ
20	8000	22	212	1,048,576
100	10⁶	1024	4.2 · 10¹¹	1.3 · 10³⁰
1000	10⁹	3.3 · 10⁹	1.9 · 10¹¹⁶	1.1 · 10³⁰¹

For n = 1000, $2^{\sqrt{n}}$ is in the same league as n³, whereas both exponentials have run off to numbers we don’t even have names for. Functions like $2^{\sqrt{n}}$ , which grow more slowly than cⁿ for any base c greater than one, are called subexponential.

The graph shows the same thing. The vertical axis is logarithmic: each tick up means a number a hundred thousand times bigger. Otherwise nothing but 2ⁿ would fit in the picture.

$Growth of 2^n (red), 1{,}307^n (orange), 2^{\sqrt{n}} (blue) and n^3 (green) with a logarithmic vertical axis$

In a graph like this, exponentials are straight lines that keep on rising. The red 2ⁿ is steeper than the orange 1.307ⁿ, but both are straight lines. Interestingly, the orange one even starts out below the green n³. It only overtakes it at around n = 42, but after that it stays ahead for good. The blue $2^{\sqrt{n}}$ , on the other hand, bends and stays down near the green one.

What exactly ETH says

Now we can state the hypothesis. It was formulated in 1999 by Russell Impagliazzo and Ramamohan Paturi:

There is a number c greater than one such that no algorithm can solve 3-SAT with n letters in fewer than roughly cⁿ steps.

In plain English? We can shrink the base of the exponential with clever tricks, from two to 1.5, to 1.307, perhaps one day to 1.2. But we will never squeeze it arbitrarily close to one. There is a limit somewhere that we can’t get below. So according to ETH, an algorithm with complexity $2^{\sqrt{n}}$ shouldn’t exist.

Why a hypothesis? Because nobody can prove it. ETH is a working assumption, much as we assume that P ≠ NP in the article on P vs. NP. Most computer scientists believe it, because decades of effort have only managed to make the base creep slowly down from two. But nobody has a proof.

ETH and P vs. NP

How are these two questions related? Imagine that 3-SAT has some “true” difficulty, the fastest possible algorithm. It can lie in one of three bands:

Three bands of difficulty for 3-SAT: polynomial (green), subexponential (blue) and exponential (red)

Green band, polynomial. 3-SAT can be solved in, say, n³ steps. Since 3-SAT is NP-complete, we would then have P = NP, and of course ETH would not hold.
Blue band, subexponential. 3-SAT can be solved in $2^{\sqrt{n}}$ steps or something similar. Not in polynomial time, so P ≠ NP holds. But ETH would not hold.
Red band, exponential. You can’t do better than cⁿ. ETH holds, and so P ≠ NP holds too.

The picture shows that ETH is a stronger statement than P ≠ NP. It says not only that 3-SAT can’t be solved in polynomial time, but that it can’t be solved in subexponential time either. Anyone who proved ETH would also have proved P ≠ NP and would win a million dollars.

And the other way round: anyone who disproved ETH would not necessarily have proved P = NP. An algorithm from the blue band is enough. Remember this; we’ll need it in a moment.

What is ETH good for?

Proving that a problem can’t be solved quickly is incredibly hard in computer science. We can hardly prove anything of the kind. ETH gives us a back door: instead of “problem X is hard” we prove “problem X is hard if ETH holds”.

How? We show that if problem X could be solved quickly, 3-SAT could be solved quickly too. Take this one, for example: we have n people and we know that some pairs of them can’t stand each other. We want to split them into three rooms so that no such pair ends up in the same room. Computer scientists call this colouring a graph with three colours. Any 3-SAT problem can be turned into a problem of this kind in such a way that the number of people is only a few times the number of letters. So if people could be split into rooms in subexponential time, 3-SAT could be solved in subexponential time too, and ETH would fall.

There are hundreds of conditional results like this today. The whole field that studies exactly how hard individual problems are stands on ETH like a house on its foundations.

ETH also has a stronger sister, the strong exponential time hypothesis (SETH). It looks at problems where conditions may have more than three letters, say ten or a hundred. SETH says that the longer the conditions we allow, the closer the best possible base gets to two. So for long conditions there would be almost nothing to save compared with blindly trying all 2ⁿ possibilities.

Why is everyone talking about ETH now?

In October 2026 OpenAI, the company best known for ChatGPT, published a preprint, that is, a paper that hasn’t been peer-reviewed yet. It is called The Exponential Time Hypothesis is False. In it, OpenAI claims to have found an algorithm that solves 3-SAT in roughly

$2^{\frac{n}{\sqrt{\ln n}}}$

steps. So the exponent isn’t n itself, but n divided by the square root of the (natural) logarithm. That denominator grows terribly slowly, but it does grow, and that’s enough to make the function subexponential. The algorithm can reportedly do even more than find one solution: it can count how many solutions there are.

If this were true, the algorithm from OpenAI would fall into the blue band in the picture above. And what would that mean?

ETH would fall, and with it SETH and the hundreds of conditional results that were built on them. Computer scientists would have to throw out or rewrite a lot of “if ETH holds, then…” results.
It would not settle the P versus NP problem. The algorithm still isn’t polynomial.
In practice almost nothing would change. The formula hides constants that we don’t know. If they were equal to one, for n = 1000 we would get $\sqrt{\ln n}$ of about 2.6 and roughly 2³⁸⁰ steps. That’s almost the same as 1.307¹⁰⁰⁰ ≈ 2³⁸⁶ for today’s best algorithms. The new algorithm would only pull clearly ahead of them for even larger n, and by how much depends on exactly those unknown constants. So its significance is mainly theoretical. Encryption and banking are not affected.

For now it is an unverified claim. The proof is long and technical and experts are only just starting to read it. Big announcements of solved problems have turned out to be wrong many times in the past, so for now the rule is: let’s wait and see what the experts say. We are writing this paragraph on 27 October 2026.

Solution to the party problem

You should invite Tom, Jack and Dan, but not Kate. The picture shows all 16 possibilities. Each column is one possibility: a filled circle means that the friend comes, an empty one that they don’t. The red number under a column shows the first condition that doesn’t hold. The only possibility in which all the conditions hold is framed in green.

All 16 possibilities of who to invite. The rows correspond to the friends T, J, K, D; a filled circle means they come.

And this is exactly the brute force that ETH considers almost unbeatable: sixteen columns for four friends, and for a hundred friends more columns than there are atoms in your body.