The Complexity of Poset Games

摘要

© 2022, Brown University. All rights reserved.The complexity of deciding the winner of poset games was only known to be somewhere between NC1 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 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.