The Complexity of Poset Games - Fenner, Stephen; Grier, Daniel; Gurjar, Rohit; Korwar, Arpita; Thierauf, Thomas (Journal of Graph Algorithms and Applications, 2022)
The complexity of deciding the winner of poset games was only known to be somewhere between $NC^1$ and $PSPACE$. We resolve this discrepancy by showing that the problem is $PSPACE$-complete. To this end, we give a reduction from Node Kayles.The reduction yields a 3-level poset game.Hence the compexity of 2-level games remains an interesting open question.We make some progress andgive a simple formula allowing one to compute the status of a type of two-level poset game that we call parity-uniform in polynomial time.This class includes significantly more easily solvable two-level games than was known previously. We also establish general equivalences between various two-level games. These equivalences imply that for any $n$, only finitely many two-level posets with $n$ minimal elements need be considered, and a similar result holds for two-level posets with $n$ maximal elements.