{"id":"arxiv/2610.19558","url":"https://arxiv.org/abs/2610.19558","tags":["cs.CC","cs.DM","cs.GT","math.CO"],"score":0,"title":"The Two-Level Poset Game is PSPACE-Complete","domain":"cs.CC","source":"arxiv","authors":["Kengo Hashimoto"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-14","reactions":{}}