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?

A Domino-Covering Problem

3 months ago