Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
We resolve the open problem of the computational complexity of Two-Level Poset Game by proving it is PSPACE-complete. This is achieved through a polynomial-time reduction from the Avoid True problem on positive CNF formulas, establishing a tight complexity bound for this fundamental class of combinatorial games. The result implies that even restricted poset games with a height of at most two remain computationally challenging.
Poset games, even when restricted to a height of two, are as computationally hard as any problem solvable in polynomial space.
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.