Grampa's Guide to Impossible Games
P, NP, and why some games can't be beaten by brute force
1. P: the easy ones
Grampa's first rule: computer scientists don't ask "how long does this take?" They ask "what happens when the puzzle gets bigger?"
A problem is in P (short for polynomial time) when the work grows gently. Double the puzzle and the work might double, or grow 4 or 8 times. Computers shrug that off, even for huge puzzles.
The troublemakers grow exponentially: add one more piece and the work doubles. That gets out of hand shockingly fast. Slide the bar and watch.
Gentle vs. explosive growth
Times assume a computer doing a billion steps a second. Bars count zeros, so each extra bit of bar means 10 times more work.
Six Degrees: easy for a computer
The computer checks actors one ring at a time, nearest first. Each actor is looked at once, so even millions of actors go quickly.
2. NP: easy to check
Now the big idea. Some puzzles are hard to solve, but if somebody hands you an answer, you can check it in a snap.
That's NP: "easy to check." The letters stand for nondeterministic polynomial, a fancy way of saying "fast, if you're a lucky guesser."
Every P problem is also in NP. If you can solve it fast, you can surely check it fast.
Try the little Sudoku. Solving takes some thinking. Checking takes one quick look at each row, column and box.
Solve it, then check it
Tap a blank square to cycle 1, 2, 3, 4. Each row, column and 2×2 box needs 1 through 4.
Why solving is harder
3. NP-complete: the master keys
Among the NP puzzles, some are the toughest of the bunch. Any NP puzzle can be disguised as one of them, rewritten so that solving it answers the original.
These are NP-complete. They're master keys: find a fast method for any one, and you have a fast method for all of NP.
The first was proven in 1971, a logic puzzle called SAT. Thousands have joined since, including a lot of your games.
One catch: the proofs use "any size" versions, like a Sudoku that can grow to 16×16, 25×25 and beyond. Your fixed-size games are small enough for a computer to grind through.
The master key web
Every game here can be translated into SAT, and SAT into every game. Tap a game to see what's hard about it.
4. NP-hard: at least that hard
NP-hard means "at least as hard as the NP-complete puzzles." The difference is that an NP-hard problem doesn't have to be easy to check.
Take a road trip. "Find me a route under 500 miles" is NP-complete: hand me a route and I'll add up the miles. But "find me the shortest route" is NP-hard. If you hand me a route, how do I know nothing shorter exists? I'd have to compare it to all the others.
That's the famous Traveling Salesman Problem, and every road trip in Staycation bumps into it. Add towns and watch the number of routes explode.
Plan a road trip
Tap the map to add up to 9 towns. Town 1 is home. Then have the computer try every route.
Where it goes from here
5. PSPACE: when there's an opponent
Solo puzzles have one kind of answer: a solution you can check. Two-player games are different.
"Can I force a win?" really means: I have a move, so that whatever you reply, I have a move, so that whatever you reply… all the way to the end.
The proof isn't one path. It's a whole tree covering every reply. Handing somebody that tree doesn't make it quick to check.
Many games like this land in PSPACE: problems a computer can solve with a reasonable amount of memory, even if it takes a very long time. The hardest of them are PSPACE-complete.
Every reply counts
Green dots are your turns, red dots are your opponent's. The bottom row is every position you'd have to judge.
6. EXPTIME: chess, checkers and Go
Chess, checkers and Go let positions come back again and again, so a game can wander for an enormous number of moves. That pushes them past PSPACE into EXPTIME: problems that take exponential time.
On an any-size board, all three are EXPTIME-complete: chess (1981), Go with Japanese ko rules (1983) and checkers (1984).
Here's the kicker. Mathematicians have proven that these can't be solved in polynomial time. With NP-complete puzzles we only suspect they're hard. With these, we know.
Your regular boards are a special case. Checkers on 8×8 was solved in 2007. Chess and Go haven't been, so computers win by smart guessing, not by checking everything.
How many positions?
Tap a game. Bars count zeros. The dashed line is the number of atoms in the known universe (a 1 with 80 zeros).
7. P vs. NP: the million-dollar question
Everything in P is in NP. The big question: is everything in NP also in P? Is every puzzle that's easy to check also easy to solve?
If yes (P = NP), every NP-complete puzzle has a fast method we just haven't found. If no (P ≠ NP), some puzzles are hard forever.
Since 2000, the Clay Mathematics Institute has offered $1 million for a proof either way. It's still unclaimed. Most experts bet on P ≠ NP.
Why you should care: the locks on online banking rely on math that's easy to check and hard to undo, like breaking a big number into its primes. If P = NP, those locks could be picked.
- P: easy to solve.
- NP: easy to check.
- NP-complete: the hardest of NP. Crack one, crack all.
- NP-hard: at least that hard, maybe not even checkable.
- PSPACE: two-player games that need patience, not much memory.
- EXPTIME: chess, checkers and Go. Proven hard.
- P vs. NP: is easy-to-check always easy-to-solve? Worth $1 million.
The map of hard
§0. The model of computation
Fix the alphabet Σ = {0,1}. A decision problem is a language L ⊆ Σ*. A deterministic multitape Turing machine M decides L in time T : ℕ → ℕ if for every x ∈ Σ*, M halts within T(|x|) steps and accepts iff x ∈ L. Define
DTIME(T) = { L : some deterministic TM decides L in time O(T(n)) }and analogously NTIME(T), SPACE(S), NSPACE(S). Every result below is asymptotic in the input length n = |x|. A fixed-size game (an 8×8 board, a 9×9 Sudoku) has finitely many instances and is therefore decidable in O(1); all hardness statements concern generalized families indexed by board size.
§1. The class P
P = ⋃k∈ℕ DTIME(nk)P is robust under the Cobham–Edmonds thesis: simulating a multitape machine on a single tape costs only a quadratic overhead, so the class is model-independent up to polynomial equivalence.
Growth (Step 1 slider). For every fixed k, limn→∞ nk / 2n = 0, so every polynomial is eventually dominated by every exponential. The demo compares n2 with 2n on a logarithmic axis.
Six Degrees. Given the co-star graph G = (V, E) and vertices s, t, breadth-first search computes d(s,t) in O(|V| + |E|), since each vertex is dequeued at most once and each edge examined at most twice. Hence {⟨G,s,t,k⟩ : d(s,t) ≤ k} ∈ P.
Word Search is solvable in O(r·c·m) for an r×c grid and a word of length m (8 directions per cell). Chronology is comparison sorting, Θ(n log n).
§2. The class NP
L ∈ NP iff there exist a polynomial p and a polynomial-time verifier V such that
x ∈ L ⟺ ∃ w ∈ {0,1}≤ p(|x|) : V(x, w) = 1Equivalently, NP = ⋃k NTIME(nk). Clearly P ⊆ NP (ignore the certificate), and NP ⊆ EXPTIME by enumerating all 2p(n) certificates. The complement class is coNP = { L̄ : L ∈ NP }.
Sudoku. Let SUDOKUn be completion of a partially filled n2×n2 grid. The certificate is the completed grid; verification checks 3n2 constraint groups of n2 cells each, i.e. O(n4) work, polynomial in the input size. Naive search over b blanks examines up to (n2)b fillings. For the 4×4 demo (n = 2): 12 groups, 48 cell reads, and 48 = 65,536 blind fillings.
§3. Reductions and NP-completeness
A polynomial-time many-one (Karp) reduction L ≤p L′ is a polynomial-time computable f : Σ* → Σ* with x ∈ L ⟺ f(x) ∈ L′. The relation is reflexive and transitive. L′ is NP-hard if L ≤p L′ for every L ∈ NP, and NP-complete if moreover L′ ∈ NP.
Corollary. If any NP-complete language lies in P, then P = NP. This is the "crack one, crack all" animation: composing a reduction L ≤p SUDOKU with a hypothetical polynomial Sudoku solver decides L in polynomial time. Karp (1972) extended the list to 21 problems; thousands are now known.
Generalized versions of the games in the web, each NP-complete:
- Sudoku on n2×n2 grids: ASP-complete, hence NP-complete (Yato & Seta, 2003).
- Minesweeper consistency: whether a revealed board admits any mine assignment (Kaye, 2000).
- Nonogram solvability (Ueda & Nagao, 1996).
- Battleship, the solitaire puzzle with row and column tallies (Sevenster, 2004).
- Mastermind satisfiability: whether any code is consistent with the given feedback (Stuckman & Zhang, 2005).
- Peg solitaire reduction to a single peg (Uehara & Iwata, 1990).
- FreeCell with n cards per suit (Helmert, 2003).
- Klondike with perfect information (Longpré & McKenzie, 2009).
- Mahjong solitaire with perfect information.
- Tetris with a known piece sequence: maximizing cleared rows (Demaine, Hohenberger & Liben-Nowell, 2003).
- Jigsaw and edge-matching puzzles (Demaine & Demaine, 2007).
- Crossword construction from a word list (Garey & Johnson, 1979).
The two-player Battleship you play is a different problem from the solitaire puzzle; the result concerns the latter.
§4. NP-hard problems outside NP
NP-hardness asserts a lower bound only; it places no upper bound on the problem. The halting problem is NP-hard (reduce SAT to a machine that halts iff its input formula is satisfiable), yet it is undecidable. This is why the dashed NP-hard region on the Step 7 map extends past EXPTIME.
Traveling Salesman. An instance is a complete graph Kn with weights w : E → ℚ≥0. The number of distinct Hamiltonian cycles is
(n − 1)! / 2 ~ ½ √(2π(n−1)) ((n−1)/e)n−1by Stirling's formula; the demo enumerates exactly these, discarding reversals. The decision problem {⟨Kn, w, B⟩ : ∃ tour of weight ≤ B} is NP-complete (via Hamiltonian cycle, Karp 1972). The optimization problem is a function problem, complete for FPNP (Krentel, 1988), and deciding whether a given tour is optimal is coNP-complete (Papadimitriou & Steiglitz, 1977). The best known exact algorithm, Held–Karp dynamic programming, runs in O(n2 2n).
Rubik's cube: deciding whether an n×n×n configuration can be solved in ≤ k moves is NP-complete (Demaine, Eisenstat & Rudoy, 2018). Pac-Man: the generalized level-clearing problem is NP-hard (Viglietta, 2012).
§5. PSPACE and alternation
PSPACE = ⋃k∈ℕ SPACE(nk)NP ⊆ PSPACE, since certificates can be enumerated in reused space. By Savitch's theorem, NSPACE(s) ⊆ SPACE(s2) for s(n) ≥ log n, so PSPACE = NPSPACE.
The quantifier alternation is precisely the game semantics of Step 5: player 1 has a winning strategy iff
∃ m1 ∀ m2 ∃ m3 ⋯ : the resulting play is a win for player 1.If play is polynomially bounded, depth-first minimax evaluates this using polynomial space while visiting up to bd leaves, where b is branching factor and d is depth. Formally, AP = PSPACE (Chandra, Kozen & Stockmeyer, 1981). A winning strategy is a tree, not a path, so it is not a polynomial-size certificate in general, which is why such games are not believed to lie in NP. PSPACE-complete examples include generalized geography (Schaefer, 1978), Hex (Reisch, 1981), a generalized Chinese checkers (Kasai, Adachi & Iwata, 1979), and Go without ko is PSPACE-hard (Lichtenstein & Sipser, 1980).
§6. EXPTIME and provable hardness
EXPTIME = ⋃k∈ℕ DTIME(2nk)PSPACE ⊆ EXPTIME, since a machine using space p(n) has at most 2O(p(n)) configurations. When positions have polynomial size but repetition lets play run exponentially long, alternation needs polynomial space, and APSPACE = EXPTIME (Chandra, Kozen & Stockmeyer, 1981).
Therefore every EXPTIME-complete language lies unconditionally outside P. Generalized n×n chess (Fraenkel & Lichtenstein, 1981), Go under Japanese ko rules (Robson, 1983) and checkers (Robson, 1984) are EXPTIME-complete.
For the fixed standard boards the asymptotic theory is silent, and the questions become finite computations. Checkers on 8×8 has about 5 × 1020 positions and was weakly solved as a draw (Schaeffer et al., 2007). Chess has about 4.8 × 1044 legal positions (Tromp's estimate). Go on 19×19 has about 2.08 × 10170 legal positions, computed exactly by Tromp and collaborators in 2016. For comparison, the observable universe has about 1080 atoms.
§7. P vs. NP
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, P ≠ EXPTIMESo at least one inclusion in the chain is strict, but which one is unknown. The central question is whether P = NP, and it is one of the seven Clay Millennium Prize Problems (2000), carrying a $1,000,000 award.
- Ladner's theorem (1975): if P ≠ NP, there exist NP-intermediate languages, in NP but neither in P nor NP-complete.
- Factoring, in decision form "does N have a factor ≤ k?", lies in NP ∩ coNP. It is therefore not NP-complete unless NP = coNP. If P = NP, factoring is polynomial and RSA falls; more generally, one-way functions cannot exist.
- If P = NP, the polynomial hierarchy collapses to P, and on the map P, NP and the NP-complete set coincide (up to the trivial languages ∅ and Σ*). EXPTIME-complete games remain outside P regardless, by §6.
- Barriers. Any resolution must evade relativization (Baker, Gill & Solovay, 1975), natural proofs (Razborov & Rudich, 1997) and algebrization (Aaronson & Wigderson, 2009).
The consensus conjecture is P ≠ NP. It remains open.