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.


