Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete

DOI10.1007/978-3-642-39206-1_42MaRDI QIDQ5326586zbMATH OpenOpenAlexFDO

Authors Daniel Grier

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.1750

Mathematics Subject Classification ID

Partial orders, general (06A06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05)

Abstract: 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.

Recommendations

• On the complexity of computing winning strategies for finite poset games
• The complexity of poset games
• The game total domination problem is log-complete in PSPACE
• Time-Optimal Winning Strategies for Poset Games
• Game Characterizations and the PSPACE-Completeness of Tree Resolution Space
• scientific article; zbMATH DE number 7075886
• Winning ways of weighted poset games
• PSPACE-Hardness of some combinatorial games
• Finitary winning in \({\omega}\)-regular games

Cited in

(10)

• Pomax games -- a family of integer-valued partizan games played on posets
• Complexity of the game domination problem
• Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game
• Strings-and-coins and nimstring are PSPACE-complete
• The complexity of poset games
• On the complexity of computing winning strategies for finite poset games
• The Ungar games
• Nimber-preserving reduction: game secrets and homomorphic Sprague-Grundy theorem
• A general upper bound for the runtime of a coevolutionary algorithm on impartial combinatorial games
• Flipping the winner of a poset game

This page was built for publication: Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326586)