  Partially-ordered set games, also called poset games, are a class of
two-player combinatorial games. The playing field consists of a set of
elements, some of which are greater than other elements. Two players take turns
removing an element and all elements greater than it, and whoever takes the
last element wins. Examples of poset games include Nim and Chomp. We
investigate the complexity of computing which player of a poset game has a
winning strategy. We give an inductive procedure that modifies poset games to
change the nim- value which informally captures the winning strategies in the
game. For a generic poset game G, we describe an efficient method for
constructing a game not G such that the first player has a winning strategy if
and only if the second player has a winning strategy on G. This solves the
long-standing problem of whether this construction can be done efficiently.
This construction also allows us to reduce the class of Boolean formulas to
poset games, establishing a lower bound on the complexity of poset games.
