Thursday, November 15, 2012

A Simple PSPACE-Complete Problem

Back in the typecast last month I promised a simple PSPACE-complete game in a future post. Here it is:


Given: A collection of finite sets S1,...,Sk.

The Game: Each player takes turns picking a non-empty set Si. Remove the elements of Si from all the sets Sj. The player who empties all the sets wins.

This game came up in a discussion I had with Steve Fenner trying to extend his student's work that Poset Games were PSPACE-complete. The PSPACE-completeness of determining a winner of the SET GAME is an easy reduction from from Poset Games.

An open question: Do we still get PSPACE-completeness if the size of the Si are bounded? I don't even know the answer if the sets have size at most two.

1 comment: