A formula drawn as a game

The complexity of a game is usually a statement about the opponent. Generalised geography is hard because each player’s move rearranges what the other can do, so that deciding a position means answering a run of alternating quantifiers. Games on boards inherit the same structure and are PSPACE-complete, or worse. When a game has no such structure, the difficulty goes away: on a plain finite graph with no memory of how the token arrived, working backwards labels every position as won, lost or drawn in time proportional to the arcs. It is one of the cheapest computations in the subject.

Something odd happens on that same cheap graph. What a stable set knows about a draw showed that the stable sets of a graph are the lost positions plus a stable set of the drawn part, and that whether a stable set exists is decided entirely in the drawn part. Labelling writes D on the drawn part and stops. The next question, whether that part has a stable set, sounds as if it should be equally routine: there are no quantifiers in it, no opponent, only two conditions on a set of vertices and a check that takes one pass. Yet Václav Chvátal showed in 1973, two years after Cook and one after Karp, in a report of the Centre de Recherches Mathématiques in Montreal, that deciding whether a directed graph has a stable set is NP-complete.

The proof is pleasant to look at, and it has the unusual property that it can be drawn as a game and then checked on every small case. It takes a formula and builds a graph out of the two smallest loops already met in these essays: the two-way pair, which has two stable sets, and the triangle, which has none.

Two gadgets, and each is a game already met #

Start with a formula in the standard form, an “and” of clauses, each clause an “or” of three literals. The construction makes one small piece per variable and one per clause.

A variable is a two-way pair. One position is named x and the other not-x, with moves in both directions. As an even cycle it has two stable sets, and nothing else in the graph has a move out of it, since these are the only moves their positions have. So any stable set of the graph contains exactly one of the two, because including both breaks independence, and including neither leaves the pair with no way of being covered. Choosing a stable set therefore chooses a truth assignment. The choice is free: nothing later can force or forbid it.

A clause is a triangle. Three positions move round in a cycle of three, and each of them additionally has one further move, out to one of the clause’s literals. The triangle by itself has no stable set. Those outward moves are the only way out of that fate. A corner whose literal is in the set has a move into the set, so that corner is covered. Once at least one corner is covered this way, the rest can be resolved around it.

The second figure shows what goes wrong when the clause is unsatisfied. All three literals are out of the set, so all three outward moves lead outside it, and they cover nothing. Now the three corners must form a stable set among themselves and that is exactly what a cycle of three cannot do. So the assignment extends to no stable set of the whole graph. This is the same argument as the one that made the triangle the first example of a game without a solution. Its role here is a clause reporting failure.

If a clause has at least one true literal, the triangle can always be completed, and only in one way. A corner whose literal is true has a move into the set, so it cannot be a member itself. A corner whose literal is false has no such help, and whether it joins the set depends on the corner it moves to around the triangle. If all three literals are true, no corner joins and all three are covered from outside. If one is false, that corner has nothing covering it: its literal is out and the next corner round is out. So it must join, which breaks nothing, since no move from it reaches a member. If two are false, take the false corner whose next corner is the true one. That corner has no cover, and so it must join. The other false corner moves to it and is covered. So the existence of a stable set extends to the formula exactly when each clause has a true literal, which is the definition of being satisfied, and each satisfying assignment extends in exactly one way.

That last clause is stronger than the reduction needed, and it is a useful thing to know. The number of stable sets of this graph equals the number of satisfying assignments. So counting stable sets is as hard as counting solutions to a formula, and asking for a second stable set is as hard as asking for a second satisfying assignment. A graph can have a large number of stable sets and give no easy way to find any.

The formula in the first figure can be worked through in a line or two. It says (x or y or z) and (not x or not y or z). The only assignments it rejects are the one making x, y and z all false, which fails the first clause, and the one making x and y true and z false, which fails the second. Six of the eight remain, and the search finds six stable sets. Take x true, y true and z false, and try anyway: the first triangle has two covered corners and takes its third, the one aimed at z. The second triangle’s three literals are not x, not y and z, all false, so it has nothing covering any of its corners, and no assignment inside it works.

Checked over every small formula #

A reduction like this is a proof, and it needs no sample. But it is cheap to check, and the check is worth doing, because several small details could go wrong: a triangle with the wrong orientation, or a corner moved to the wrong literal, would not be visible in an argument at this level of informality.

There are eight clauses that use all three variables, one for each pattern of signs, so 255 non-empty sets of them. All but one are satisfiable, since each clause rules out exactly one assignment of the eight, and only the formula with all eight clauses rules them all out. On each formula the search for a stable set and a direct check of the assignments agree. The one formula with no satisfying assignment has no stable set, on a graph of thirty positions, in which each individual piece is unremarkable.

The last row of that table is what this essay is really about. On all 255 formulas, every position is drawn. The two-way pairs have no way to lose: neither position is ever without a move. The triangles have no way to lose either, because every position has a cycle move. So the whole of every one of those graphs has no position with no move, and the backward labelling never gets started. It looks at the graph and writes D on every position in one pass. The two conditions then ask a question about that graph with the D’s on it, and that question is satisfiability.

So outcome labelling, which runs in linear time and answers the question the whole subject is about, sees no difference at all between a formula that is satisfiable and one that is not. A game with all positions drawn is, in that framing, the most uninteresting game there can be. It is also, by this construction, precisely where the hard instances lie.

What the search costs and what the labelling costs #

The table measures a plain backtracking search on Chvátal’s graphs of random formulas, at the clause density known to be hardest for such searches. It decides one position at a time, starting with the variables, and gives up on a branch as soon as a position can no longer be covered. At four variables and 17 clauses, a graph of 59 positions, it takes a median of 165 steps. At sixteen variables and 69 clauses, 239 positions, it takes 871,268. That is a factor of about 5,000 for a factor of 4 in the size of the formula, and fits doubling for each added variable. The arcs in the same graphs go from 110 to 446. That is what the labelling costs, and on these graphs it returns nothing informative at any price.

The numbers are a measurement of one simple search on the hardest density, and they should be read as a caption to the theorem and not as evidence for it. A strong satisfiability solver would do far better on formulas this small, so the real difficulty only appears at sizes this table never reaches. What the table can demonstrate is a qualitative difference: one column grows by additions and the other by multiplication. And nothing is known that escapes that in general, since doing so for all formulas is exactly what is meant by P versus NP.

Five questions and one hard one #

Set side by side, the questions a graph can be asked about itself fall into a pattern that looks strange until it is explained.

The first and the third are the surprising pair. They use the same graph, the same definition of a move, and nearly the same two conditions. A labelling is a function from positions to three values, and a stable set is a function from positions to two values, and the two constraints are almost word-for-word the same. Why should adding a value make the problem easy?

The answer is the D itself. A labelling is allowed to say “not settled” about any position, and that makes each constraint one-sided: a position is labelled lost only when all its moves are already known to be won. The rounds can run in any order and they never have to go back, because the labels only ever accumulate. A stable set has no third value. Every position has to be in or out, and every position has to justify that immediately. So a decision about one position can force decisions about others, around a cycle, and a choice made early can come back around and clash. The drawn value is exactly the licence not to make that choice. It is what lets the labelling avoid the search. And it is not a value, as the essay on draws argued, for much the same reason: it marks where the rounds stopped rather than recording what was found.

The second and third are the other familiar pair. Checking a proposed stable set takes one pass over the arcs. That is why the problem is in NP at all, and a stable set is a certificate in the ordinary sense, which is more than can be said for a winning strategy in general. A game’s winning strategy usually cannot be checked without working through its replies, which is the distinction at the centre of PSPACE. The stable set’s status is one level lower down. So on one small graph there are three different levels of question: the outcome is in P, the existence of a stable set is NP-complete, and the question of who wins if each vertex can be visited only once is the PSPACE-complete geography. What separates them has nothing to do with the graph. It is only what the question asks about that graph.

The last two rows are where the question becomes easy again, for structural reasons already shown. With no cycle, the stable set is what the labelling already found. With no odd cycle, Richardson’s construction finds one in polynomial time and existence is automatic. Marriage tables are easy for yet another reason. All the hard instances must be outside those families, and the construction here confirms that they are: every variable pair is even and every clause triangle is odd, and it is those triangles that carry the information.

Later work has pushed the hardness a long way down. Aviezri Fraenkel showed in 1981 that the question stays NP-complete on planar graphs in which no position has more than two moves or can be moved to from more than two others, so nothing about the difficulty needs a dense or tangled graph.

Why a game of draws is the right place for it #

It would be easy to take the construction as a trick, a formula dressed in graph notation, and to think that the game has nothing to do with it. The reason it is more than that is the way each part behaves as play. A variable is a pair of positions a token could pass back and forth between for ever. A clause is a cycle of three the token could go round for ever, unless someone steps out. Nobody is ever forced into anything; every position has a move, and no line of play ends. As a game it is a perfectly valid object with a one-word solution.

What changes is the question put to it. A stable set asks for a policy with no memory that covers every position at once, the kind of thing a player could write down once and consult forever, without looking at the history. Asking whether such a policy exists turns out to be asking for an assignment that satisfies all the clauses simultaneously. Each clause is a place where the policy might break down because of a cycle, and each variable is a place where it has a free choice, and the choices must work for all the clauses at once. The difficulty is global consistency in a policy, and no opponent’s cleverness is involved. That is why the complexity lands at NP and not at PSPACE: there is one thing to find, with no alternation, and once it has been found it can be checked. The game supplies the graph and the loop, and the definition of 1944 supplies the demand that one set of positions should answer for all of it.

The convention underneath #

The result is about a digraph with no extra rule, and the reading of arrows as moves is the one these essays have been using all along. The formula’s clauses have three literals each, because this is the standard hard form and because a triangle has three corners. Clauses with fewer literals need a different gadget, and satisfiability with two literals a clause is easy, so nothing here should be read as saying every graph containing a triangle is hard.

The word “hard” is a statement about worst cases over all graphs and assumes that P differs from NP, which is unproved. The theorem itself is that a fast algorithm for stable sets would give a fast algorithm for every problem in NP, and it stands on any resolution of that question. Nothing here says that any particular small graph is hard. Graphs of a few hundred positions of this kind are usually easy for a modern solver.

What the tables cannot show #

That the labelling could never help. The reduction shows that on some graphs labelling sees nothing, and every one of the graphs drawn here is such a graph. It does not show that on natural games with draws in them, such as a chess fortress, the drawn part is anywhere near this hard. Natural games have far more structure than a random formula, and no measurement here addresses which side of the line they fall on.

Whether stable sets of real games are worth computing. The point of the essay is that this object can be hard. It has not been established that any actual player needs it. On a position that is drawn, a stable set gives a guarantee of not losing, and any simple rule that keeps the draw gives the same guarantee, in practice, without any search at all.

That doubling continues. The search column is seven points, and the fit to a doubling rate is a fit. The theorem does not state any rate. How far a strong solver can move that curve at these densities is a question about solvers rather than about the graph.

Still open: whether games can be hard in this way #

The construction draws a formula as a game, but the game is not one anyone would play. The hardness comes from a tailored arrangement of pairs and triangles, and a position in any traditional game has a much more regular graph. The question this leaves is whether a real game, one with draws and with a rule set not built for the purpose, has a drawn part in which finding a stable set is genuinely difficult. A solved game would be the place to look: an endgame table is a labelling of a large graph with its drawn part intact, and asking how much of that part admits a stable set is a measurement these essays have not made.