Thursday, September 20, 2012

Poset Games are PSPACE-complete

Consider the following game on a poset, each player takes turns picking an element x of a finite poset and removes all y ≥ x. First one to empty the poset wins. I posted last March about a high school student, Adam Kalinich, who showed how to flip the winner of a poset game.

Finding the winner of a poset game is in PSPACE by searching the game tree. A corollary of Adam's work showed that poset games were hard for Boolean formula leaving a huge gap in the complexity of finding the winner.

Daniel Grier, an undergrad at the University of South Carolina, has settled the problem and shows that determining the winner of a poset game is PSPACE-complete. His reduction is ridiculously simple (though not obvious) and the proof is not that complicated either.

Grier starts from Node Kayles which is a game on an undirected graph where each player takes turns removing a vertex and all its neighbors. Whomever empties the graph first wins. Thomas Schaefer showed the PSPACE-completeness of Node Kayles back in 1978.

Grier's reduction from Node Kayles to posets is very simple: Let G be the graph. Have one element in the poset for each vertex of G, all incomparable. For each edge e=(u,v) we add two more elements, one above the vertex elements corresponding to u and v, and one below every vertex element other than u and v. That's the whole construction.

Grier shows that if G has an odd number of edges and no immediate win for the first player then the first player wins the Node Kayles game if and only if the first player wins the corresponding poset game.

You can read more details in Grier's short paper. It's really neat seeing high school students and undergrads solving interesting open problems. We need more problems like poset games.

6 comments:

  1. Hmm, I seem to remember that in Chomp[1] (a POSET game) the first player always wins. Does this got disproven?

    [1]: http://en.wikipedia.org/wiki/Chomp

    ReplyDelete
    Replies
    1. That still holds. Grier's result is about general poset games. The Chomp family is an easy restriction of the general problem.

      Delete
    2. Is Chomp easy to solve in general? As far as I remember, it's known that the first player on a full-rectangular board has a winning strategy, but it is not at all constructive.

      Delete
    3. You did know well. I only read about it, no so experienced about.

      Delete
  2. But suppose the situation is that the first player always wins for general POSET, yet it takes cost of PSPACE complete to find the winning strategy, the game is still PSPACE complete, or not?

    ReplyDelete
    Replies
    1. No, I don't think so. PSPACE (and most other complexity classes) deal with languages, i.e., questions that have YES/NO answers. In the POSET game case, "Is there a strategy for player one to win?" There is no requirement for a machine that solves such a problem to actually produce the proof. So, if this is indeed the case, a machine can just report YES on all (relevant) inputs and thus solve he problem efficiently. Compare for instance with COMPOSITE and FACTORING. In COMPOSITE you ask if a number is composite, answerable in polynomial time, whereas actually producing the prime factors takes exponential time.

      Delete