## Thursday, March 27, 2014

### 2048 is in NP

(This post assumes some familiarity with the game.)

### Turning interactive games into pen/paper puzzles

In computer science, $NP$ is the collection of all the types of pen/paper puzzles whose solutions are easy to double-check (but not necessarily easy to find). These span a wide range of difficulties, from mazes to Sudoku to who owns the zebra?-style logic puzzles.

(Formally, $NP$ is the set of decision problems for which yes answers can be verified in polynomial time.)

Of course, 2048 is a Category 1 life-threatening memetic contagion video game, not a pen/paper puzzle. So we're going to need to do a little bit of massaging to talk about it as if it was.

That's where Tetris comes in.