The Complexity of Sliding-Block Puzzles (PDF)

Mathematicians have discovered that sliding block puzzles are hard because they are hard in a mathematical sense. Their complexity is PSPACE-complete, which is thought to be harder than NP-complete. In this paper, the author shows how to construct logic gates in a sliding block puzzle. Therefore, you could construct a sliding block puzzle that corresponds to a mathematical problem, and the puzzle would have a solution only if the math problem does!

Hey, this could be a great way to solve the Riemann Hypothesis. Just make a sliding block puzzle that corresponds to the RH, give it away to people with lots of spare time, like kids and seniors, and wait for some unsuspecting puzzler to solve it. (Although, I have a hunch that the physical implementation of an RH puzzle would end up being hundreds of miles in diameter.)

(via Ed Pegg's article at MAA Online)