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
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?
A Domino-Covering Problem
2 weeks ago