A puzzle asks once, a game asks alternately

Here is a question about a boolean formula: is there an assignment of true and false to the variables that makes it come out true? That is a puzzle. Somebody who has solved it can prove it by handing over the assignment, and checking takes a moment.

Here is a second question about the same formula: is there a value for $x_1$ such that, for every value of $x_2$, there is a value for $x_3$ … making it come out true? That is a game. The two questions are about identical objects and they are not the same kind of question at all.

The prefix is the order of play #

Read a quantifier prefix left to right and it is a sequence of turns.

$\exists x_1$ is the mover chooses. $\forall x_2$ is the opponent chooses. $\exists x_3$ is the mover again. The formula at the end is the rule for who won: if it comes out true, the existential player has won; if false, the universal player has.

That is not an analogy dressed up. It is the definition of the truth of a quantified formula, restated, and it is why the object is called a game in the literature rather than merely being compared to one. A prefix of $n$ alternating quantifiers is an $n$-move game, and asking whether the formula is true is asking who wins it.

The reason the alternation is the load-bearing part becomes visible as soon as the two quantifiers are priced separately.

What each quantifier costs whoever has to check #

Somebody claims the existential player wins. What must they produce?

For a plain existential — a prefix of nothing but $\exists$ — the answer is one assignment. It is $n$ bits long, and checking it means substituting and evaluating, which is a single pass over the formula. That is the shape of every problem in NP: hard to find, cheap to check, and the thing checked is small.

Add one universal and the shape breaks. The claim is now there is a first move such that, whatever the reply, the rest works out — and there is no single assignment that establishes it. A proof must cover every reply, so it is one first move plus an answer to each of the opponent’s options, which is a tree rather than a string.

Each universal quantifier multiplies the number of lines that must be covered. A prefix with $k$ universals needs $2^k$ lines answered, and the object doing the answering is a strategy.

The bottom of that ladder is worth drawing, because it is the case with no game in it at all.

Nothing about that is a game, and the machinery does not pretend otherwise: the witness is one line, so the strategy and the assignment are the same object. Making the formula unsatisfiable moves the six-vertex graph rather than changing what kind of thing the answer is.

Add the alternation and the object on the other end of the claim changes kind rather than size.

The reduction, and why it is a game people can play #

A quantified formula with its alternating prefix is already a game, and a rather abstract one. The result that matters turns it into a game on a graph that a person could sit down and play.

Generalized Geography: a token sits on a vertex of a directed graph; a move slides it along an edge to a vertex not yet used; a player who cannot move loses. The rules take one line and there is nothing logical about them.

The reduction builds, from any quantified formula, a graph on which the existential player wins exactly when the formula is true. The completeness result works through why that is enough; what matters here is the shape of the thing built.

The construction is one gadget repeated. Each variable becomes a small diamond with two routes through it, and the token’s route records the assignment. The diamonds are chained so that they are traversed in the order of the prefix, which makes the alternation of quantifiers into the alternation of turns — the whole point of the construction. At the bottom sits a challenge vertex where the universal player picks a clause, and the existential player must then point at a literal in that clause that the earlier choices made true.

Everything hangs on that last step. The existential player can answer the challenge exactly when the assignment satisfies every clause, because the universal player will pick the worst one.

The check that could have failed #

A reduction is an argument that two questions are the same question, and an argument of that kind is worth testing rather than admiring.

Both sides are computed here, independently, on every formula over three variables, and the two agree on all 255. That is worth more than a proof sketch in prose, and there is a trap in it recorded in this site’s own notes: an earlier version of the test tried to demonstrate that it could fail by inverting every literal in every clause, and all 255 still agreed — because inverting every literal renames each variable to its own negation, and the game is symmetric under that. The break that works is handing the challenge vertex to the wrong player. A test that never rejects anything is not a test.

The break turns out not to need introducing, and finding that out is what makes the sweep evidence rather than decoration. An even number of variables hands the challenge to the wrong player on its own. Each diamond costs three moves, so after an even number of them it is the existential player who is to move at the challenge vertex — and the existential player naming the clause it wants to be asked about is not the argument at all.

So the failing case was inside the construction the whole time, and it is not a corner: at four variables the reduction answers a different question about more than half of all formulas. What follows is that the reduction refuses an even prefix rather than returning a graph, and that the sweep at three variables is now a claim with a demonstrated alternative rather than a claim with none.

Walking one formula through #

It is worth following the token once, because the gadget is easier to see moving than described.

Take three variables and the prefix $\exists x_1 \forall x_2 \exists x_3$. The token starts at the top of the first diamond, and the existential player is to move: the two edges out are set $x_1$ true and set $x_1$ false. Whichever they take, the token arrives at the bottom of that diamond and continues to the top of the second, where it is the universal player’s turn and the same two-way choice is theirs. Third diamond, existential again.

After three diamonds the assignment is written on the board — it is the route the token took — and the token reaches the challenge vertex, where the universal player picks a clause. The existential player must then move to a literal vertex inside that clause, and may only move to one the token has not already used. The vertices used up are exactly the literals made false by the assignment, because the route through each diamond consumed the side it went down.

So the existential player can answer exactly when the chosen clause contains a literal the assignment made true. The universal player will of course choose the clause that fails if any does. The game therefore ends with the existential player stuck precisely when some clause is unsatisfied — which is the formula being false.

That is the entire proof of one direction, and it is a construction rather than an argument: every piece of the formula became a piece of a board. The essay on the completeness result works through why the other direction — that the game is no harder than the formula — is the easy half.

The same shape without any logic in it #

Nothing about this depends on the game being built out of a formula. Alternation is in the rules of every game this site draws, and the hardness results that exist for particular games are all this pattern instantiated.

Amazons is PSPACE-complete as a family. So is Domineering, which is a striking thing to learn about a game whose entire rulebook is one sentence. Sprouts is harder to place and its three-spot case is not settled by the solver here at all. Hex, Go with certain rulesets, and generalised versions of most board games people play sit in the same class.

What makes them all land together is not a shared structure in the games. It is that each is rich enough to simulate an alternating choice of bits, and once a family can do that, it inherits the difficulty of the thing it is simulating. This is why hardness proofs for games nearly always look like engineering: they build wires, gates and crossovers out of board positions, and the mathematics is in checking that the pieces behave.

The moral for a reader looking at a small board is worth repeating, because the two are so easy to mix up. The family being complete for a class says nothing about the board in front of them. The board in front of them is nine squares and this solver settles it in a millisecond.

NP, PSPACE, and what is actually known #

The two questions at the top of this essay sit in two named classes, and it is worth being exact about what is known, since this is a place where careful statements get repeated as sloppy ones.

Satisfiability — one existential, a witness that is an assignment — is NP-complete. The quantified version, with alternation, is PSPACE-complete, which is the same statement Generalized Geography satisfies through the reduction above.

Every problem in NP is in PSPACE: an exhaustive search over assignments needs only the space to hold one assignment at a time. Whether the containment is strict is not known. It is believed, in the same way that P ≠ NP is believed, and it has not been proved.

So the honest form of this essay’s claim is not games are harder than puzzles. It is: the natural game question is complete for a class that contains the natural puzzle question, and every reason anybody has to think the classes differ is a reason to think games are harder. The alternation is what moves the problem from one class to the other; whether that move crosses a real boundary is one of the open questions of the subject.

What that move looks like as the prefix lengthens is worth one more figure, because the two quantities in it grow at completely different rates.

That is the growth the whole essay is about, and the two columns grow at different rates. The graph grew from fourteen vertices to twenty-six, which is linear in the number of variables. The witness grew from one line to four, which is exponential in the number of universals — and it is the second column that decides which complexity class the question lands in.

Where alternation goes missing #

A game with alternation in its rules can still lose it in particular positions, and those positions are where all the cheap answers live.

A position whose value is a number has nothing left to fight over: numbers avoid numbers, neither player wants to move in one, and the outcome follows from the sign without any search. A Cutcake position is a number always, which is why the whole family is settled by looking at two integers.

An impartial game keeps its alternation but throws away the asymmetry, and the Sprague–Grundy theorem then collapses the whole tree to a single number. Nim is decided by three exclusive-ors at any size, and the alternation is still there in the rules — it has simply been solved once and for all rather than searched each time.

The pattern is worth stating: alternation is what makes the general question hard, and a theorem is what makes a particular family easy in spite of it. Neither fact touches the other. Nim being easy is not evidence against Geography being hard, and Geography being hard is no reason to search a Nim position.

No chooser, one chooser, two choosers #

Lining up the three cases makes it clear how narrow the middle of this subject is.

No chooser. A position with no moves is settled by the convention: under normal play whoever is to move has lost. Everything in the subject is built on that one line, and it is the base case every recursion stops at.

One chooser. A puzzle. Solitaire, sudoku, whether a graph can be coloured — a single existential, a witness that is small, and a check that is quick. Some puzzles are extremely hard to solve and every one of them is easy to verify, which is the property that makes the class what it is.

Two choosers, alternating. A game, and the object that certifies a claim about it stops being small. It is also the first case in which the opponent can be the one with the answer, which a puzzle has no room for at all.

Nothing of that kind is available with one chooser. A puzzle with no solution is a puzzle nobody can establish anything about cheaply — there is no short certificate of unsatisfiable either — whereas here the universal player holds a strategy of exactly the same shape as the existential player’s, and it is two lines long.

There is a fourth case, and it is the one that breaks the recursion rather than the complexity. If play can return to a position it has already visited, the alternation goes on for ever and the question changes: a loopy game may end in neither player winning, and a draw is an outcome that no value represents. That is a failure of a different kind — not an answer out of reach, but a question the machinery was not built to ask — and it is worth its own rung.

What the picture cannot show #

Three limits, and the first is the one most often lost.

Hardness is about a family and an encoding, never a position. Nothing in the reduction says any drawn graph is hard. It says that the family of graphs produced by the reduction is at least as hard as the family of formulas — a statement about how the cost grows as the objects grow. Any particular graph on this page is settled by the solver here in milliseconds.

A reduction is a lower bound in one direction only. It says Geography is at least as hard as quantified satisfiability. Combined with the easy direction — a Geography game can be decided in polynomial space by playing it out with a stack — it pins the problem to the class exactly. Only the pair of arguments gives completeness, and only the completeness makes it a statement about the class rather than about one problem.

Complete does not mean unsolvable. These are all decidable questions with straightforward algorithms; what the classification claims is that no algorithm anybody has found does better than exponential time on the worst cases, and that finding one would collapse a great many other problems at the same time.

Who proved it, and when #

Quantified boolean satisfiability was shown complete for polynomial space by Stockmeyer and Meyer in 1973, which is the result everything here rests on. Even and Tarjan proved Generalized Geography PSPACE-complete in 1976, and Schaefer in 1978 carried the same treatment through a long list of games people actually play, establishing the pattern that has held ever since: generalise a board game to arbitrary size, and the natural question about it lands in PSPACE.

The lasting contribution is not the list. It is the recognition that the quantifier prefix — a piece of logical notation — is the same object as the sequence of turns, so that every game with two players moving alternately, no chance and no hidden information is a formula with an alternating prefix wearing a board.

The easy direction, which is the whole reason the class is space #

The reduction above is the hard half of the completeness argument. The easy half — that the question is in PSPACE at all — is usually waved through in a clause, and it is worth writing out, because it explains why the class this subject lands in is named after memory rather than after time.

Play the game out depth-first. Hold the current position, whose turn it is, and the list of moves already tried at each level of the current line; when a line ends, back up one level and try the next move there. Nothing else is stored. No table, no set of visited positions, no record of any line that has been finished with.

The memory that costs is therefore one line of play, and a line of play is short. Every move in these games consumes something that cannot come back — a square filled, a vertex visited, a counter removed — so the depth is bounded by the size of the board rather than by the number of positions on it. A 4×4 Domineering board has 5,700 positions and 6,257,129 routes, and its deepest line is eight moves.

The time is another matter entirely: the search visits every route, and the routes are exponential. So the algorithm is cheap in the resource the class is named for and ruinous in the other, which is exactly the trade the definition of PSPACE permits.

That is the sharpest available statement of the difference between a puzzle and a game. For a puzzle the thing kept in memory is a certificate — an assignment, handed over and checked. For a game the thing kept in memory is a path, and everything already explored is thrown away and re-derived if it is ever needed again. One class is about what can be stored; the other is about what can be recomputed cheaply enough not to store.

It also says why memoisation is an optimisation here and never a change of class. A table of visited positions turns the exponential time into something smaller and turns the polynomial space into exponential space, which is the wrong direction for the classification and the right one for an afternoon. The algorithm that puts the problem in PSPACE is precisely the one nobody would run.

Where the ladder goes next #

alternation opens here, with the quantifier prefix and the sequence of turns identified as one object.

The rung the closing figure points at is the certificate, and it is in the complexity anchor rather than this one. “Left wins” has no short proof measures the object an alternating claim has to produce, on positions this solver settles completely, and the numbers are worth the trip: a complete solution of Nim on heaps of 7, 11 and 13 is 480 table entries, and a winning strategy from that single position is 56,167,022 nodes. The proof of one line is a hundred thousand times the size of the answer to all of them.

That page also supplies the argument this one leaves as an expectation. If a game question had short certificates it would be in NP, every PSPACE problem would follow it there, and PSPACE’s closure under complement would then give $\mathrm{NP} = \mathrm{co\text{-}NP}$. So the natural game question is complete for a class containing the natural puzzle question is not merely suggestive: making the two coincide collapses a hierarchy, which is the reason nobody expects it.