IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

The Difficulty of Finding Winning Strategies for Poset Games

  • March 21, 2013
  • 3:45 p.m.
  • LeConte 312

Abstract

A poset game is a mathematical strategy game played over a partially ordered set (poset) in which two players alternate choosing an element of the poset, removing it and all elements greater than it. The first player unable to select an element of the poset loses. Quick algorithms for finding the winner of a poset game exist in certain restricted cases such as the popular game of Nim. The complete solution for the game of Nim has been known since 1901, but there is still no algorithm for quickly solving the more general poset game problem. In this talk, I will give a reduction showing that this problem is almost assuredly computationally infeasible. More precisely, the reduction shows that deciding the winner of an arbitrary finite poset game is PSPACE-complete. The proof relies on the PSPACE-completeness of Node Kayles, a game in which players vie to chose an independent set in a graph, but otherwise requires no background in computational complexity.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC