Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete
verfasst von : Daniel Grier
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A poset game is a two-player game played over a partially ordered set (poset) in which the players alternate choosing an element of the poset, removing it and all elements greater than it. The first player unable to select an element of the poset loses. Polynomial time algorithms exist for certain restricted classes of poset games, such as the game of Nim. However, until recently the complexity of arbitrary finite poset games was only known to exist somewhere between
NC
1
and
PSPACE
. We resolve this discrepancy by showing that deciding the winner of an arbitrary finite poset game is
PSPACE
-complete. To this end, we give an explicit reduction from Node Kayles, a
PSPACE
-complete game in which players vie to chose an independent set in a graph.