The Complexity of Poset Games
Vol. 26, no. 1, pp. 1-14, 2022. Regular paper.
Abstract The complexity of deciding the winner of poset games was only known to be somewhere between $\textsf{NC}^1$ and $\textsf{PSPACE}$. We resolve this discrepancy by showing that the problem is $\textsf{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 and give 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.

 This work is licensed under the terms of the CC-BY license.
Submitted: April 2020.
Reviewed: October 2021.
Revised: October 2021.
Accepted: October 2021.
Final: November 2021.
Published: January 2022.
Communicated by Gerhard J. Woeginger
article (PDF)