Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 24 min ago
PreprintarXiv licencearXiv

The Two-Level Poset Game is PSPACE-Complete

  • Kengo Hashimoto
Open at sourcePDFDOICite

Abstract

Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.

Related

  1. Arc Kayles is PSPACE-complete
    Édouard Bonnet
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
    Lasitha Jayasinghe
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Limit Theorems for the Complete Feedback Card Guessing Game
    Partha S. Dey, Jaya M. Manthripragada
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  4. A Deterministic Game-Theoretic Approach to Convexity-Preserving Property and Finite-Time Extinction of Level Sets for Geometric Equations
    Yousuke Saga, Kazuhiro Takimoto
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  5. Hodge level and effective non-vanishing for smooth weighted complete intersections
    Victor Przyjalkowski
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{hashimoto2026twolevel,
  title = {{The Two-Level Poset Game is PSPACE-Complete}},
  author = {Kengo Hashimoto},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.19558},
  eprint = {2610.19558},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.19558},
}
RIS
TY  - UNPB
TI  - The Two-Level Poset Game is PSPACE-Complete
AU  - Kengo Hashimoto
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.19558
UR  - https://arxiv.org/abs/2610.19558
AB  - Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.
ER  -