Complexity of Two-Level Poset Game
Given a finite poset of height at most , consider the normal-play poset game in which a move selects an element and removes together with every remaining element satisfying . Determine the computational complexity of deciding whether the first player has a winning strategy.
References
- The Two-Level Poset Game is PSPACE-Complete — arXiv — Kengo Hashimoto
Source: arXiv
Progress summary
The general two-level case remains open, with no independently verified breakthrough found.
The problem asks for the computational complexity of deciding the winner in general poset games of height two. The established hardness result applies at height at least , while the height-two case remains unresolved.
Known results
- Finite poset games of height at least are -complete via a reduction from Node Kayles.
- Parity-uniform height-two games have polynomial-time algorithms.
- Duplicate neighborhoods can be reduced modulo parity.
- Fixed numbers of minimal or maximal elements yield finite reductions.
Current status (as of October 2026): The general height-two problem remains open, and no verified resolution is recorded.
Solutions 0
No solutions have been posted yet.