In my last post, I talked about the Exponential Time Hypothesis (ETH), and how it applies to puzzles. Here I’m going to roughly outline the disproof of the hypothesis.
I’m following a graduate level lecture by Ryan O’Donnel, with additional background reading. More specifically, I’m following the first half of the lecture, because I gave up on understanding or explaining the rest. My goal is to convey a broad conceptual understanding, and flavor.
Puzzles inside other puzzles
Have you ever heard of people creating working computers inside Minecraft? Have you heard that Magic: The Gathering is Turing complete? Some game systems are complex enough that in principle, you can program anything inside of them, including another game. And so, you can program Minecraft inside Minecraft (link to video).
Puzzles are like this as well. You can program puzzles inside of other puzzles. You can make a sokoban puzzle whose solution is equivalent to solving a sudoku. And then you can make an origami crease pattern, where figuring out how to fold it is equivalent to solving a sokoban. I mean, you could do it in principle, although it would be horribly inefficient in practice.
Sudoku, sokoban, and origami crease patterns are all part of a class of puzzles called “NP-complete”. You can think of it like “Turing complete”, but for puzzles. If a puzzle is NP-complete, that means any NP problem can be programmed inside of it. So if you can solve an NP-complete problem, then in principle you can solve any NP problem.
To prove that a problem is NP-complete, you don’t have to go down the list of every other NP problem and explicitly program them one by one. Usually you pick a “canonical” NP-complete problem, and just program that one.
The formal statement of ETH refers to an NP-complete problem known as 3SAT, or the “boolean 3-satisfiability problem”. But 3SAT itself isn’t important, any NP-complete problem will do for our proof.
SAT, 3SAT, and #3SAT
SAT refers to the “boolean satisfiability problem”. You are presented with a boolean formula, and asked whether it is possible to satisfy it. For example:
((x and z) or y) and not x
This formula can be satisfied with x=False, y=True, and z can be anything.
Complexity theorists often work with a slightly simpler problem called 3SAT. 3SAT presents you a series of boolean expressions, each of which uses up to three variables. We can think of SAT and 3SAT as basically equivalent.
Note that as long as we can calculate whether there’s a solution, then we can also explicitly construct a solution. First, assume x is true. Then calculate whether any solutions remain. If there’s no solution, then set x to be false. Repeat the process with each variable until a solution has been constructed.
On the other hand, suppose we wanted to count the number of solutions. That seems to be harder. #3SAT (“#” may be pronounced “Sharp”) refers to the problem where you count the number of solutions to the boolean formula. #3SAT belongs to a class of problems called #P-complete. #P-complete is at least as difficult as NP-complete, although it’s not known whether it’s more difficult or equally difficult.
ETH formally refers to the 3SAT, but the disproof goes one step further, by finding an algorithm to solve #3SAT. And it immediately substitutes another #P-complete problem, known as computing the permanent.
The heterosexual pairing problem
The “permanent” is a function in matrix algebra, similar to the determinant. I’m going to illustrate it means with an analogy.
Suppose that we have N men and N women. Our objective is to put everyone into heterosexual pairs that like each other. The question is, how many different solutions are there?
To give an example:
Alice and Charlie like each other.
Alice and David like each other.
Beatrice and David like each other.
This problem has a single solution: pair Alice with Charlie, and Beatrice with David.
You can also describe the solution with a matrix:

The “permanent” of the matrix is equal to the number of solutions to the heterosexual pairing problem.
(Nobody calls it the heterosexual pairing problem but me. It’s formally known as the bipartite graph perfect matching problem. But I described the problem to my husband and he immediately dubbed it the heterosexual pairing problem.)
The permanent was proven to be #P-complete by Valiant’s Theorem in the 70s. The theorem basically shows you how to program a #3SAT problem into a matrix permanent. A version of this theorem appears in the ETH disproof.
Computing the permanent
Eventually we need to stop translating problems into other problems, and actually figure out how to solve one of them. The disproof of ETH finds a sub-exponential method of calculating the permanent of a matrix. I’m going to outline the steps, but I’m sure I’ll lose people here, so feel free to skip to the next section. Or if you’re a math person who wants more details, go nuts and watch the lecture.
So we have a matrix M, and we’re trying to calculate the permanent perm(M). The algorithm constructs matrices M1, M2, M3 etc. with some special properties. We use them to create a matrix polynomial in t.
M(t) = M + M1t + M2t2 + M3t3 + …
The variable t doesn’t have any meaning, except that if we compute M(t=0) that’s just our original matrix. We can define a function
P(t) = perm(M(t))
The value that we’re trying to compute is simply P(t=0). This is hard.
But when we constructed Mi, we gave them a special property: it’s “easy” to calculate P(t=1), P(t=2), P(t=3) and so on. It’s also “easy” to calculate the Nth derivative of P(t) at those points.
Ultimately, P(t) is a polynomial. So if you find enough points on the curve, and enough derivatives, then you can basically deduce what the whole polynomial is. Then you compute P(t=0) and we’re done. The total computation time is about O(exp(N/sqrt(log(N))).
Concluding thoughts
Will this help me solve sudoku? Emphatically no. I am not going to solve a sudoku by translating it into 3SAT, translating into a matrix permanent, and turning the matrix into a polynomial of matrices. Not even the computers are going to solve it that way.
But it’s an upper bound on the problem complexity, which applies to every NP problem ever. And the upper bound ends up being such a weird expression. It makes me wonder, can we do even better?

Leave a Reply