The Exponential Time Hypothesis in puzzles


The Exponential Time Hypothesis (ETH) is a conjecture in computational complexity theory. One inexact way of stating the ETH is, “Some puzzles require brute force to solve.” I think the ETH is intuitively true, to the extent that I have asserted it on this blog without naming it.

So I was shocked to learn that ETH is false. It was recently disproven by LLMs from OpenAI and Anthropic. I’m very interested to understand why.

ETH is relevant in many areas, but in this post I will describe its relation to recreational puzzle solving. In another post, I’ll very roughly outline the proof. I’m not going to talk about the LLM aspect at all.

Computational complexity

Computational complexity theory is the theory of problem difficulty. Specifically it describes how long it takes for a computer to complete a task. For example, take the task of solving a sudoku.

If we’re talking about the sudoku puzzle that appears in today’s newspaper, there exists a computer algorithm that will solve it instantly. Just hardcode the solution into the algorithm, and you’re done. Yes it may have taken the programmer a while to come up with the solution, but the algorithm itself takes no time at all.

And in principle, there are “only” 10^81 sudoku puzzles. In principle, the programmer could hardcode every single solution into the algorithm. So in a sense, the question of how long it takes to solve sudoku is ill-posed.

So instead, when we talk about the complexity of sudoku, we include sudoku puzzles of all sizes. There are 9×9 sudokus, 16×16 sudokus, 25×25 sudokus, and beyond. That’s an infinite number of sudoku puzzles, and we want a general algorithm that can (eventually) solve any of them. Computational complexity theory asks how long that algorithm takes, as a function of puzzle size.

P and NP

The theory describes several classes of problems. “P” refers to problems whose computational time is a polynomial in the problem size. For example, a jigsaw puzzle can be solved in a time that is proportional to the number of pieces squared. Therefore, jigsaw puzzles are P.

Some jigsaw puzzles have thousands of pieces, so N^2 sounds pretty slow. But it could have been much worse than that, it could have been 2^N. So you can think of “polynomial time” as being relatively fast, and “exponential time” as being relatively slow.

“NP” refers to problems where a solution can be verified in polynomial time. For example, you can quickly verify that a jigsaw puzzle solution is correct by checking that all adjacent pieces match correctly. Therefore jigsaw puzzles are NP, in addition to being P.

Every single problem in P is also in NP. However, it is conjectured that some problems are in NP but not in P. In other words, it is conjectured that some problems are slow to solve, but quick to verify a solution. If the conjecture is true, then Sudoku is one of these puzzles. Sudoku cannot be solved in polynomial time, but you can check whether a solution is correct in polynomial time. The conjecture (known as P≠NP) is widely believed, but mathematicians have famously been unable to find a proof. For purpose of this discussion, I’m going to take it for granted that P≠NP.

Puzzles and complexity

Where do recreational puzzles belong within computational complexity theory? Generally, we want puzzles to be quick to verify. “Did I successfully solve the puzzle or not?” is not supposed to be part of the challenge. So puzzles are usually in NP.

Are puzzles also P? Some puzzles, such as jigsaw puzzles and rubik’s cubes are in P.  Jigsaw puzzles take N^2 time, which is polynomial time but still slow in practice. Rubik’s cubes (including cubes of arbitrary size) can also be quickly solved by an algorithm, but perhaps the puzzle is finding an algorithm and executing efficiently.

Other puzzles, including Sudoku and Sokoban, are not in P. In the general case, solving these puzzles is slower than any polynomial. (And before the ETH was disproven, I would have said it was exponentially slow.) Of course, it doesn’t seem that way in practice; it’s perfectly possible to solve sokoban puzzles within a reasonable time frame.

The key point is that puzzles do not ask you to solve the general case. You are presented instead with a specific sokoban puzzle, often made by a puzzle designer with intent. The designer does not want you to apply a general algorithm, they want you to come up with new ideas to solve each new puzzle.

So the function of computational complexity in a puzzle is to discourage or prevent general solutions. The general solution is too slow to be practical. Instead, you have to play to the specific puzzle, following the breadcrumb trail left by the designer.

Brute force

But there exists a general solution that works on nearly every kind of puzzle. It’s called brute force (also sometimes called “branching” or “guessing”). Basically, you try things until you find something that works.  Brute force is usually considered undesirable, but puzzle solvers often end up doing it at least a little.

The number of possibilities to try grows exponentially with the size of the puzzle. For example, in a sudoku puzzle, the first digit can be anything from 1-9, which is 9 possibilities. The second digit can be anything 1-9 which is another 9 possibilities, for a total of 9×9=81. For each digit in the puzzle, you multiply the number of possibilities by 9. You can think of it as a giant tree of possibilities, where each digit is a new branching point.

Of course, you can be smart about it, pruning lots of branches as you go. But in the general case, you can’t eliminate every branch, and that’s more or less what it means to say that Sudoku is not P.

That’s why the ETH makes so much sense to me. Some puzzles require brute force, and brute force is exponentially slow, therefore the ETH is true. When discussing logic puzzles in the past, I didn’t know the ETH by name, but I was already asserting that it was true.

But the ETH is false. That implies that not a single puzzle in NP requires brute force. No, not even one!

Although, hold your horses. Although the solution is faster than exponential, it’s still slower than any polynomial.

The new algorithm takes something like 2^(N/sqrt(log(N)). You can think of this as being very similar to brute force, except that you’re able to prune more and more branches as you go deeper and deeper. Imagine that after the first 10 digits of the sudoku puzzle, you can deduce half of the remaining digits. After the first 10^4 digits, you can deduce two thirds of the remaining digits. After the first 10^9 digits, you can deduce three quarters of the remaining digits. And so on.

This is not a practical method that’s going to break any puzzles.  This is a “galactic algorithm” that eventually beats brute force, but not within the timescale of the universe.  Still, it’s very counterintuitive to me that it’s possible.

Leave a Reply

Your email address will not be published. Required fields are marked *