High Schoolers and undergrads are awesome at Poset Games

A few weeks back, the Computational Complexity Blog had a great post about a PSPACE-completeness proof about games!  Even cooler, the result was found by an undergrad at the University of South Carolina!

This is the third result about games on partially-ordered sets (posets) from young researchers that I've heard of.  In 2003, Stephen Byrnes proved a cool theorem about the periodicity of chains in poset games.  Earlier this year, Adam Kalinich found a transformation that converts a current-player-is-winning poset game to an other-player-is-winning poset game.  (I'm less familiar with this result; I'm not sure whether it's assumed that these are all impartial games.)  Now, Daniel Grier has shown that the General Poset Game is PSPACE-complete.

What exactly is the General Poset Game?  It's a game played on elements of a partially-ordered set.  Each turn, a player removes an element from the set as well as all elements greater than the chosen element.  If there are no elements in the set at the beginning of your turn, then you can't make a move and lose the game.

Many games are examples of poset games, including Chomp and Nim.  This result does not immediately mean those games are PSPACE-complete to determine which player is winning!  (Nim is definitely not, since there's an easy way to evaluate Nim states.)  This says that the following problem is hard: given a set, S, and a partial ordering of S, P, determine whether the General Poset Game using P on S is in Fuzzy or Zero.  Thus, worst-case instances are going to be difficult, not just ones that are easily recognizable as a Nim state.

The reduction for this is extremely simple!  I'm out of time, however!  More next time! :)