Geodesic
The Complexity of Poset Games
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 1, pp. 1-14.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00578
Keywords: Poset games, PSPACE, Complexity 
@article{JGAA_2022_26_1_a0,
     author = {Stephen Fenner and Daniel Grier and Rohit Gurjar and Arpita Korwar and Thomas Thierauf},
     title = {The {Complexity} of {Poset} {Games}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {1--14},
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2022},
     doi = {10.7155/jgaa.00578},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00578/}
}
TY  - JOUR
AU  - Stephen Fenner
AU  - Daniel Grier
AU  - Rohit Gurjar
AU  - Arpita Korwar
AU  - Thomas Thierauf
TI  - The Complexity of Poset Games
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 1
EP  - 14
VL  - 26
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00578/
DO  - 10.7155/jgaa.00578
LA  - en
ID  - JGAA_2022_26_1_a0
ER  - 
%0 Journal Article
%A Stephen Fenner
%A Daniel Grier
%A Rohit Gurjar
%A Arpita Korwar
%A Thomas Thierauf
%T The Complexity of Poset Games
%J Journal of Graph Algorithms and Applications
%D 2022
%P 1-14
%V 26
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00578/
%R 10.7155/jgaa.00578
%G en
%F JGAA_2022_26_1_a0
Stephen Fenner; Daniel Grier; Rohit Gurjar; Arpita Korwar; Thomas Thierauf. The Complexity of Poset Games. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 1, pp. 1-14. doi : 10.7155/jgaa.00578. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00578/

Cité par Sources :