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,
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! :)
A Domino-Covering Problem
5 weeks ago