Twelve turns, and three different prices

A puzzle asks once, a game asks alternately prices a universal quantifier and stops. Each one doubles the number of lines a winning claim has to answer; a prefix with three of them needs eight lines answered; the object doing the answering is a strategy rather than an assignment. All of that is true and none of it is a measurement, because it counts the opponent’s turns and says nothing about when they happen.

The counting is wrong, and it is wrong by a factor of sixty-four over twelve turns.

The term that does the work #

A strategy is not a list of moves. It is an answer to every line the opponent can produce, so a decision made after $k$ of the opponent’s turns has to be recorded once for each of the $2^k$ ways those turns could have gone.

That gives the size of a strategy in one line: sum $2^k$ over the chooser’s own turns, where $k$ counts the opponent’s turns before each of them. Nothing else enters. The number of clauses does not, the number of variables does not except through the sum, and — this is the part the doubling account misses — the number of the opponent’s turns does not either. Only their positions do.

Three turns for each player, taken in strict alternation, gives $1 + 2 + 4 = 7$. The same three turns each, with the chooser taking all of theirs first, gives $1 + 1 + 1 = 3$: the opponent has done nothing yet, so there is one line to answer and the strategy is an assignment. The same three turns each again with the opponent going first gives $8 + 8 + 8 = 24$, because every one of the chooser’s decisions has to be written out for all eight of the opponent’s openings.

Three, seven and twenty-four, from one set of turns rearranged. The quantity that orders them is how many times the choosing changes hands, and a run of consecutive turns by one player is one such change rather than several. That run is what the literature calls a block, and the arithmetic above is the reason the word exists.

Every arrangement, counted #

One example is an example. The census is over every prefix there is.

The middle rows are the finding. Four turns with two of them the opponent’s can cost two decisions or eight; with three of them the opponent’s, one or eight. The count of the opponent’s turns is fixed down each row and the cost is not, which settles the question a puzzle asks once leaves open: how many universal quantifiers is not the measurement.

The extremes are worth reading as well, because they are the two cases with no game in them. Four turns all belonging to the chooser cost four — an assignment, one bit a turn, and the shape of every problem in NP. Four turns all belonging to the opponent cost nothing at all, because the chooser has nothing to decide; the claim is then a claim about every assignment, and its refutation is what somebody would have to write down.

That second reading is the one this essay has to take seriously, and it arrives below.

There is also a shape in the table that is easy to read past. The cheapest arrangement in every row is the one with the opponent’s turns at the end, and the dearest is the one with them at the start, with every mixture in between. That is not a coincidence and it is not an ordering by block count either — two of those arrangements have the same number of blocks. It is the sum reading itself out: a term is $2^k$ where $k$ counts opponent turns already taken, so pushing an opponent turn later moves it out from under every one of the chooser’s remaining decisions at once. Moving one turn one place can halve the total, and moving it across all of them can divide by a power of two.

Why the doubling story was not wrong #

None of this contradicts the doubling account. A universal quantifier does double the lines a claim must answer, and the doubling is visible in every column of the census. What the doubling does not do is compose into a total, and that is the step where an intuition about quantifiers goes astray.

The trouble is that the doubling applies to the decisions after it and to nothing else. An opponent turn taken last doubles nothing, because there is nothing behind it to double; an opponent turn taken first doubles every decision there is. Three doublings is therefore a range rather than a number — it is a factor of eight applied to some suffix of the chooser’s decisions, and which suffix depends on the arrangement.

Put the other way round: the number of the opponent’s turns bounds the ratio between the cheapest and the dearest arrangement, and says nothing else. Three opponent turns among four give a spread of exactly eight, four among eight give a spread of sixteen, and the count of universals is exactly the logarithm of the spread. So that earlier essay’s quantity is a real quantity measuring a real thing; it simply measures the width of the range rather than a position in it.

That is a familiar shape in this subject. Knowing who wins and knowing what it is worth separates two questions about one position that a single number was being asked to answer; here two quantities have been separated out of one word.

The three growths #

Carried out, the arrangements do not merely differ. They separate.

At twelve turns with six of them the opponent’s, the three arrangements cost 6, 63 and 384 decisions. The chooser-first arrangement grows linearly — one decision per turn, for ever. The alternating one doubles every two turns. The opponent-first one doubles every two turns and carries a factor of six in front of it, because each of the chooser’s six decisions has to be written out for all sixty-four of the opponent’s openings.

Sixty-four times, between the cheapest and the dearest, on prefixes that are identical in every respect an accounting of quantifiers can see.

It is worth being exact about what that does and does not show. It is not a hardness result; a formula over twelve variables is settled by looking at all four thousand and ninety-six assignments, and nothing here is beyond a moment’s arithmetic. What it shows is that the object certifying the answer — the thing somebody would have to be handed in order to check a claim without redoing the work — is of a completely different size in the three cases, and that the difference is invisible to the quantity a count of universals sees.

Which side of the claim is small #

There is a second reading of the same three arrangements and it reverses one of them.

A claim about a quantified formula has two sides. The chooser can be right, in which case a winning strategy is what establishes it; or the opponent can be right, in which case a refutation is, and a refutation is the same object with the two players exchanged. Both were computed above and only one was reported.

The opponent-first arrangement was the dearest of the three and is now the cheapest, because the six the chooser could not produce is exactly the six the opponent can: whoever moves first with all their turns at once simply writes their assignment down. So the two-block prefixes are cheap on one side and ruinous on the other, and which side is which is decided by who opens.

The alternating prefix has no cheap side. Sixty-three one way and a hundred and twenty-six the other, and both grow exponentially.

The asymmetry between the two numbers in that last pair is worth a sentence, because it is the only place the arithmetic is not symmetric. Six turns each, taken alternately, with the chooser opening: the chooser’s decisions sit after zero, one and two of the opponent’s turns and the opponent’s sit after one, two and three of the chooser’s. Whoever moves second pays for one more doubling than whoever moves first, all the way down, so the second player’s object is exactly twice the first’s. Under a convention where the player who cannot move loses, moving first is worth a factor of two in what has to be written down and nothing at all in who wins.

That is the sharpest statement available of what a block is worth, and it is the one that connects to the classes. A prefix of two blocks is a question with a short answer available to somebody — which is the definition of a problem in NP, or in its complement — and a prefix whose turns alternate throughout is a question with a short answer available to nobody. “Left wins” has no short proof is that fact about a game; this is the same fact about the prefix the game is equivalent to, and the arithmetic is three lines long.

What the evaluator actually pays #

The strategy size is arithmetic on the prefix and asks nothing of a computer. What a machine pays to decide the formula is a separate question, and it is measured rather than derived.

The evaluator is the definition read as a program: at one of the chooser’s turns, try the branches and stop at the first that comes out true; at the opponent’s, stop at the first that comes out false. Both early exits are available, and they are available because the two players want opposite things — the one property of an alternating question that helps rather than hinders.

A single block costs two leaves of sixteen, on average over all 65,535 formulas: the evaluator finds a satisfying assignment or a falsifying one almost at once and stops. Four blocks cost 6.83, better than three times as much. So the alternation is expensive in the measured sense as well as in the certificate sense.

But the rise is not monotone — three blocks cost 5.16 and two cost 5.40 — and that is a finding rather than noise. An early exit fires when a branch comes out the way the player wanted, so its frequency depends on how often the formula is true, which is a property of the formula and not of the prefix. A prefix that is true on nine formulas in ten prunes well at the chooser’s turns and badly at the opponent’s; the arrangement decides which kind of turn there are more of; and the two effects need not pull the same way. The certificate size has no such interference, which is why it is the cleaner instrument and why the essay leads with it.

The honest form of the claim is therefore narrow: more blocks cost more in every accounting here, and only the certificate accounting is monotone in them.

Where the exponent sits #

One more piece of arithmetic is worth extracting, because it is the whole reason a bounded number of alternations is a different subject from an unbounded one.

For the alternating arrangement the exponent is the number of turns. For either two-block arrangement the cheap side’s exponent is nothing at all — it is linear — and the dear side’s exponent is the number of the opponent’s turns, which for a fixed arrangement is half of them. So the difference between the arrangements is not a constant and not a polynomial factor: it is a difference in what the exponent is a function of.

A question whose prefix has a fixed number of blocks, however many variables it has, therefore has a certificate of a shape that does not change as the formula grows. A question whose prefix alternates all the way down does not. That distinction is what the polynomial hierarchy is, and it is why the completeness results in this subject are about generalised families rather than about big boards — the family is complete and the board is settled in a millisecond is the same observation from the other end.

It also says exactly what would have to be true for a board game to land somewhere easier. A game whose length is bounded independently of its size — where a fixed number of moves ends it however large the board gets — has a prefix with a fixed number of blocks and is not PSPACE-complete by this route. Nothing here is such a game. Every family here ends because every move consumes something that cannot come back, so the length grows with the board and the blocks grow with the length.

What a small board looks like in this accounting #

It is worth putting one of the positions here through the arithmetic, because the numbers are smaller than the discussion suggests and that is itself informative.

Three Nim heaps of 3, 4 and 5 have a longest line of twelve moves. Read as a prefix with one turn a quantifier, that is twelve blocks, and the strategy the arithmetic above predicts is sixty-three decisions. The strategy for a Nim position is measured in an earlier essay and it is not sixty-three; on heaps of 7, 11 and 13 it is fifty-six million nodes.

The gap is not an error in either count. It is the assumption this essay has been making since its first line: a turn is one bit. A Nim turn is a choice among twelve moves at the opening and among fewer later, and a choice among twelve is not a choice among two. Every turn on a real board is several quantifiers rather than one, so the prefix a board is equivalent to is longer than the game by a factor nobody here has measured.

Which means the three curves are right about prefixes and are a lower bound on boards. The cheap arrangement is available to a formula and not to a game, because a game with one player taking six turns in a row is not a game anybody plays — a rule that hands a player a second move is exactly the rule the ordinary conventions forbid, and every family here alternates by construction.

The convention this rests on #

Every count here reads the prefix left to right as the order of play, with the chooser moving first wherever the prefix begins with their turn. That is the identification a puzzle asks once makes and it is doing real work: the whole arithmetic is a statement about when a decision is made relative to the opponent’s, and a prefix read in any other order would give different numbers.

Two smaller conventions are worth naming because they are choices rather than facts.

A strategy is counted in decisions, not in bits. Each of the chooser’s variables contributes one decision per line it has to be written for, and a decision is a single bit here because each variable is boolean. On a board where a turn is a choice among many moves the two counts come apart, and that is a different measurement.

The formulas are every non-empty selection from the clauses that name each variable once. That is 65,535 of them over four variables, which is exhaustive over that family and is not exhaustive over all formulas — a clause naming two of four variables is not in the sweep. The census is therefore a statement about a stated family, and the certificate arithmetic above is a statement about the prefix alone and holds whatever the clauses are.

What the picture does not settle #

The certificate is not the cost of finding it. Everything here sizes the object that establishes an answer. Nothing says how long it takes to produce one, and the two are famously not the same: the cheap arrangement’s three-bit strategy still has to be found, and finding it is the satisfiability problem.

A block is not a turn and the two are being compared on purpose. The whole reading is that the second count is the right one and the first is not, which is a claim about these prefixes and this cost model. A different accounting — one that charged for the verification as well as for the object — would order the arrangements differently, and the opponent-first arrangement is where it would differ most.

And nothing here is asymptotic. Twelve turns is twelve turns. The three curves separate on the range drawn and the algebra says they go on separating, but a measurement over a finite range is a measurement over a finite range, and the class names in the table are names for the shapes rather than theorems established on this page.

Still open: what a board’s prefix actually looks like #

The three arrangements above are constructed. A real game supplies its own, and nothing here says which.

Two things would have to be measured. The first is whether a board’s turns really do alternate all the way down — a rule that lets a player move twice, as a capture in Dots and Boxes does, merges two turns into one block and shortens the prefix by exactly the arithmetic above. The second is more awkward and is the one this essay has quietly assumed away: a turn in a prefix is one bit, and a turn on a board is a choice among however many moves there are. A board with eight moves at a turn is three quantified bits rather than one, so the prefix a game is equivalent to is longer than the game, and possibly much longer.

Until that is measured, the count of blocks on a board is a count of turns, and the turns are not the units this essay has just spent itself arguing against.