Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-019 | 31st January 2013 18:03

On Two-Level Poset Games


Authors: Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf
Publication: 1st February 2013 10:41
Downloads: 2878


We consider the complexity of determining the winner of a finite, two-level poset game.
This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.
We give a simple formula allowing one to compute the status of a type of two-level poset game that we call parity-uniform.
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.

ISSN 1433-8092 | Imprint