Two-level poset game proven computationally hard to solve
The Two-Level Poset Game is PSPACE-Complete
Computational ComplexityDiscrete MathematicsComputer Science and Game Theory
Summary
Poset games are a type of puzzle where players take turns removing items based on rules about order. Some well-known games like Nim and Chomp are poset games. People knew that playing these games on structures with a height up to three was very hard for computers to solve, but it was unclear for two-level structures. The authors show that even when the game is restricted to just two levels, deciding the winner is still very hard for computers, making the problem PSPACE-complete.
What this means in practice
- •For algorithm designers: Exclude efficient algorithms for deciding outcomes in two-level poset games, guiding them toward heuristic or approximate methods.
- •For complexity theorists: Use the result to better classify the difficulty of related combinatorial games and complexity problems.
A theory result. No direct application yet.
Authors
Kengo Hashimoto
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.