Friday, October 26, 2012

Poset Games, a Clarification

One possible misconception from Daniel Grier's recent paper showing that the general partially-ordered set (poset) game is PSPACE-complete is that this property applies to all poset games.  Thus, Nim and Chomp are also PSPACE-complete.  For those who know the quick trick to evaluating Nim states, this doesn't quite match up.  Determining whether a Nim position has a win for the next player can be done very quickly.  What's wrong here?  Does this mean that PSPACE = P?

The unexciting answer is: No.  The issue is that Nim is played on very specific types of partially ordered sets.  The posets in Nim lend to this trick of quick evaluation.  Chomp also uses specific types of posets, and thus it also isn't immediately known to be PSPACE-hard.  (I believe it's unknown whether Chomp is a hard problem for either NP or PSPACE.)

One nice aspect of Grier's proof is that it uses posets that have chains (a <= b <= c <= d <=... <=z) with only three elements (a <= b <= c).  Thus, if you have another ruleset that has potential positions including all posets with chains of 3 (or 3 levels of elements) then that game is also PSPACE-complete.  Chomp's posets do not include all sets with chains of 3, so we can't directly infer that Chomp is PSPACE-complete.

Are there any rulesets out there that satisfy that condition?

No comments:

Post a Comment