Nim is easy, in binary

A Nim position of three heaps, each holding 1,048,576 counters. Writing it in binary takes sixty-three digits. Laying it out on a table takes three million counters and most of the afternoon.

The nim-sum takes three exclusive-ors in both cases.

The claim that needs a ruler #

Nim is easy is a sentence this site has used repeatedly and it is incomplete as it stands. Easy means the work is small compared to the input, and a position can be written down in more than one way.

Take three heaps of a thousand. Written as three numbers in binary that is thirty bits, and the nim-sum’s three exclusive-ors is work proportional to the input: linear, and unimprovable, since an algorithm must at least read what it is given.

Written as counters — three thousand of them in a row, which is how the game is actually played — the same three exclusive-ors are work proportional to the logarithm of the input. The algorithm now looks better than linear, absurdly so: it settles a position of a million symbols with three operations.

Nothing about the algorithm changed. The ruler changed, and complexity is a statement about a ratio, so changing the ruler changes the statement.

The gap between the two rulers is not a fixed factor either. It opens as the heaps grow, and it opens exponentially.

Which ruler is the right one #

The convention is that the input length is the number of symbols needed to write the instance down in a reasonable encoding, and reasonable is doing real work in that sentence. It means, roughly, an encoding no more than polynomially longer than the shortest sensible one — so binary and decimal are interchangeable, and unary is not.

This is not fussiness. It is the difference between two genuinely different problems:

• Given heap sizes in binary, who wins? The instance is short and there are exponentially many positions of that length.
• Given a row of counters, who wins? The instance is long, and an algorithm may take time proportional to it while doing almost nothing clever.

An algorithm that is polynomial in the value of a number but exponential in its number of digits is called pseudopolynomial, and the reason the word exists is that the distinction has bitten a great many people. Nim is not one of the victims: three exclusive-ors is linear in the digits, which is the strong version of the claim.

Where the same distinction bites #

The place this matters most on this site is not Nim, which is easy under either ruler, but its neighbours.

A subtraction game is settled by the mex rule, running left to right: the value of a heap of $n$ needs the values below it, so a strip of Grundy values has to be built from the bottom and the work is one step per value. That is linear in $n$ — and $n$ written in binary is $\log_2 n$ digits, so the computation is exponential in the length of the input. A heap of a billion counters is a ten-digit number and a billion steps.

Nim escapes this and its neighbour does not, on the same input written the same way, which is why the distinction cannot be waved away as bookkeeping. The nim-sum reads the digits; the mex rule reads the counters.

Except that it is not, because these sequences are eventually periodic and the period is a proof. Once the period is known, a heap of a billion is settled by a division: reduce the index modulo the period and look up a value in a small table. The closed form is what rescues the encoding, and the same rescue happens over and over in this subject.

The pattern is worth naming. A table computed at every size below the one asked about is only affordable when the input is written out in full. A closed form is what makes an answer affordable when the input is written compactly, and finding closed forms is most of what the impartial theory does.

Two ways to be given a game #

There is a second encoding question underneath the first, and it is the one that decides whether a hardness result is about anything.

A game may be handed over as a position in a named family — a Domineering board of these dimensions, a Nim position of these heaps — which is short, and the family’s rules supply everything else. Or it may be handed over as an explicit graph of positions and moves, every vertex and edge listed.

The second is enormous and it makes everything easy. A game given as a graph with $N$ vertices is decided by working backwards through those vertices in time proportional to the graph, which is linear in the input. Every game is easy when the input is the whole game.

So a hardness result must be about the first kind of input, and the reduction that proves Generalized Geography complete is careful about exactly this: the graph it builds is proportional in size to the formula, not to the number of positions the game on it can reach. The game has exponentially many positions and a short description, which is the only arrangement in which the question has any bite.

The size of that gap is worth a number. Three heaps of 7, 11 and 13 are eleven binary digits to write down and have 480 distinct positions behind them, reached by 75,707,699,717,937,900 routes; a $4 \times 4$ Domineering board is two small integers and has 5,700 positions and 6,257,129 routes. In both cases the description is a handful of symbols and the graph it names is exponentially larger, and that gap is the whole reason a hardness question can be asked about a game at all.

Succinctness raises complexity, reliably #

There is a general phenomenon here and it is worth stating in its own right, because it explains a family of results that otherwise look unrelated.

Writing an object more compactly makes questions about it harder, in the exact sense of moving them up a complexity class. The object is unchanged; the ratio between the work and the input has moved, because the input got shorter.

The extreme version is a circuit or a program that generates the instance, and questions about such succinctly-described objects are routinely a full exponential harder than the same questions about the object written out. A generalised board game sits at the mild end of the same phenomenon: the rules plus the dimensions are a short description of an exponentially large game graph.

This also explains why the interesting families are always the generalised ones. Chess on an 8×8 board is a finite object with a fixed number of positions and no asymptotics at all — it is one instance, and one instance has no complexity. Generalise the board and the description stays short while the game grows, and only then is there a family to ask a question about.

Counting what a solver reads #

The clean way to keep this straight is to count what the algorithm actually touches, and to notice that different families hand it different things.

Nim’s rule reads the heap sizes and does one operation per heap, so its denominator is heaps — or, at the level of bits, one column of the binary expansion at a time, so it is digits. Green Hackenbush’s rule reads the graph and touches each edge a constant number of times, so its denominator is edges. Cutcake’s reads two integers and does arithmetic on them, so its denominator is digits again.

Set beside each other, “three steps”, “twelve steps” and “one division” are not comparable numbers. Each is small against its own input and that is the only claim any of them makes.

The habit this suggests is a small one and it prevents a specific error. When a figure on this site reports the work a shortcut does, it reports it in the units the shortcut is stated in, and the input length beside it. A step count without a denominator is a number that cannot be checked.

A position that is its own description #

Green Hackenbush is the interesting case, because there the input is neither compact nor written out — it is the object.

Twelve edges is twelve edges: there is no shorter description of this graph, and no longer one either. So the complexity question about green Hackenbush has none of the ambiguity that Nim’s has. The fusion rule is linear in the input, full stop, and the 1,283 positions the search would otherwise walk are exponential in the same input.

That is why this family is such a clean example of a theorem doing computational work. There is no encoding argument, no pseudopolynomial fine print, and no room for the claim to be smuggled in: the structural rule reads the answer off in twelve steps, and a solver that did not know it would visit 1,283 positions to reach the same number.

It also shows the other side. A graph family — lattices of $n$ by $n$ — has a short description again, and asking about the $n$-th member reopens exactly the questions this essay is about. The input is two integers; the graph is $O(n^2)$ edges; the fusion is polynomial in the graph and therefore polynomial in the input, since the graph is only polynomially larger than its description. Nothing goes wrong here, and it is worth seeing a case where the reasoning has to be done and comes out fine.

What the encoding does not change #

Three things stay put whatever ruler is used, and they are worth separating from the things that move.

The answer. Who wins is a fact about the position, and no encoding alters it. This is obvious and worth saying, because the language of complexity slides easily into sounding as though the difficulty were in the position rather than in the description.

The number of positions. Three heaps of a thousand contain a million and one distinct reachable positions however they are written. Encoding decides what the input is, not what the search space is.

The theorem. The nim-sum is the value under any encoding. What changes is whether computing it counts as cheap, and the theorem was never a statement about cost.

Where this runs out #

Two limits, and the second is the one worth carrying.

A compact encoding does not always have a compact algorithm. Domineering’s input is two integers — the dimensions — which is about as short a description as a game can have, and nobody has found any way to answer questions about it faster than searching. Shortness of description is what permits a hard family; it does not create difficulty on its own, and it does not create shortcuts either.

Nothing here says which encoding a reader should have in mind. The right answer depends on where the position came from. A Nim position that arose from a coin-turning game or from green Hackenbush arrives as a structure that must be reduced to heap sizes first, and the reduction is the cost. Quoting “three exclusive-ors” for a green Hackenbush graph would be a real overclaim: the fusion pass is linear in the edges, and the edges are the input.

The general habit this suggests: when a cost is quoted, ask what it is a cost per. Per counter, per digit, per edge and per position are four different denominators, and the same algorithm gets four different reputations depending on which one is chosen.

The encoding a player actually uses #

There is a version of this argument that is not about computers at all, and it is the reason the distinction feels artificial the first few times it is met.

A person playing Nim across a table sees counters. Nobody counts a heap of thirty into binary before deciding what to do; they look, they group, and they take. The binary encoding is a representation chosen by the analysis, and the fact that the analysis is cheap in that representation is a fact about the representation as much as about the game.

That is not a complaint. It is where the theorem’s content lies. Somebody had to notice that heap sizes should be written in binary and added without carries — an operation that appears nowhere in the rules and that nobody would arrive at by playing — and the discovery is exactly the discovery of the right encoding. The nim-sum is a change of representation with a proof attached.

Most of the closed forms in this subject have that character. Reading a Hackenbush string as a binary expansion is a re-encoding; so is collapsing a green graph to a tree; so is writing an octal game as three digits. In each case the work is done by finding the representation in which the answer is short, and the algorithm afterwards is nearly trivial.

Which is a fair description of what a theory is, in this subject: not a faster search, but a change of what the position is written as.

Who insisted on this #

The convention that input length is measured in a reasonable encoding is as old as the theory of NP-completeness itself, and it is stated with unusual care in Garey and Johnson’s 1979 book, which is also where the word pseudopolynomial was made standard. Their worked example is the knapsack problem, whose famous dynamic program is linear in the capacity and exponential in the digits of the capacity — the same shape as the subtraction game above.

For games specifically, the insistence on generalising a fixed board to an arbitrary one goes back to the same run of results in the 1970s that put Geography and its relatives in PSPACE. It is not a technicality bolted on afterwards; without it there is nothing to prove, because a fixed board is a finite object and every question about it is answerable by a table.

One last observation, since it is the thing a reader is most likely to take away and misuse. None of this makes the choice of encoding arbitrary or the results negotiable. Binary and decimal give the same classification; unary and binary do not, and the reason is not a convention anybody chose but the fact that one is exponentially longer than the other. Where two reasonable encodings disagree about a problem’s class, that disagreement is itself a result about the problem, and it is usually the most informative thing anybody knows about it.

Two inputs, two rulers #

An octal game has a feature Nim does not, and it sharpens everything above: it is handed over as two inputs of quite different kinds. The code — $\cdot 007$, three digits — describes the rule. The heap size describes the position. Complexity in the first is not complexity in the second, and the famous open problems of the family are open in exactly one of them.

Fix a code and the question who wins a heap of $n$? has one known method: run the mex rule from the bottom, which costs a pass per heap up to $n$. Write $n$ in unary and that is polynomial in the input, and the game is easy. Write $n$ in binary and it is exponential in the input, and nobody knows anything better.

So $\cdot 007$ is solved in unary and open in binary, and that is not a play on words — it is the precise content of the phrase the sequence is unsettled. What a period would supply is a way of answering a query in time polynomial in the digits: reduce the index, look up a small table, done. A period is a proof is therefore a statement about encoding as much as about pattern, and the search for periods in the octal family is a search for algorithms that are polynomial in the right ruler.

The other input behaves differently again. Vary the code rather than the heap, and the question becomes one about a family of games rather than about a family of positions — which is what the surveys sweep, and the reason a sweep of 4,095 codes is a feasible piece of work while a single code to a billion heaps is not. Two rulers, two questions, and only one of them has ever been the hard one.

Where the ladder goes next #

The complexity anchor reaches four rungs to here: how hard the games are, why Nim is not, what the encoding does to that claim, and now that the same algorithm has two reputations depending on how the position is written.

The rung above asks the question from the other side. If a hardness claim says no fast algorithm is known, the certificate version asks what would have to be handed over, and “Left wins” has no short proof measures the object. A complete solution of Nim on heaps of 7, 11 and 13 is 480 table entries; a winning strategy from that one 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 — and the nim-sum, which is a re-encoding of exactly the kind this page is about, replaces the whole of it with three exclusive-ors.

Space is the resource then names the quantity the classification actually turns on. A 4×4 Domineering board has 6,257,129 routes, 5,700 distinct positions and a deepest line of eight moves, and it is the smallest of those three numbers that gives the family its complexity class — which is why the class is PSPACE rather than something named after time.

And what solved means collects the senses of the word this ladder has been using separately. Hex is solved by an argument that names no move; Nim by a formula that names one from anywhere; between them sit strategies for a single opening and databases of a few billion positions. All four are called solved, and the distinctions between them are the distinctions this rung has been making about encodings, one level up.