Exponential Time Hypothesis

Some puzzles are easy to check but hard to solve. The Exponential Time Hypothesis is a claim about how hard one such puzzle must be.

The puzzle is called 3-SAT. You have a row of switches, and each switch is on or off. You also have a list of rules. Each rule gives up to three conditions, and at least one of them must hold. For example: $a$ is on, or $b$ is on, or $c$ is off.

The puzzle asks if some setting of the switches obeys every rule. Checking one setting is easy, because you only read through the rules. Finding a good setting is the hard part.

The simplest method tries every setting. With 2 switches there are 4 settings. With 10 there are 1,024. With 100 there are about $1.27\times {10}^{30}$, a number with 31 digits. A computer that tests a billion billion settings each second would need about 40,000 years.

Each new switch doubles the work, because each old setting now has two versions. Growth like this is called exponential. Clever methods do much better. The best methods before 2026 multiplied the work by about 1.3 for each new switch, not 2. But the work still grew by a fixed multiple, so it was still exponential.

The Exponential Time Hypothesis says that this cannot be fixed. It says that some number above 1 exists, such as 1.1 or 1.01, with this property. Every possible method must multiply the work by at least that number for each new switch, on the hardest puzzles.

Researchers used the hypothesis as a working assumption, to show that other problems are hard. The argument goes like this: if that problem had a fast method, then 3-SAT would have a method faster than the hypothesis allows.

OpenAI and Anthropic each report that the hypothesis is false. Each gives a method whose multiplier is not fixed. As puzzles grow, the multiplier for each new switch keeps falling toward 1. So no number above 1 can be a limit. Both methods also count how many settings work, not only whether one exists.

This does not help anyone solve real puzzles. The gain appears only for enormous inputs. Anthropic calculates that its method beats trying every setting only above ${10}^{10000}$ switches, when there are 5 rules per switch. That is a 1 followed by 10,000 zeros. The observable universe has only about ${10}^{80}$ atoms.

It also does not settle the famous question of P versus NP. For $n$ switches, that question asks for a method with work like $n^2$ or $n^3$, or any other fixed power of $n$. The new methods are still far slower than that.