← All problems

Complexity of Two-Level Poset Game

Given a finite poset P=(V,≤)P=(V,\leq) of height at most 22, consider the normal-play poset game in which a move selects an element xx and removes xx together with every remaining element yy satisfying x≤yx\leq y. Determine the computational complexity of deciding whether the first player has a winning strategy.

References

Source: arXiv

Progress summary

Refreshed
Open

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 33, while the height-two case remains unresolved.

Known results

  • Finite poset games of height at least 33 are PSPACE\textsf{PSPACE}-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.

Sources

Solutions 0

No solutions have been posted yet.