Maker-Maker and Maker-Breaker Games are PSPACE-Complete

Jesper Makholm Byskov

August 2004


We show that the problems of deciding the outcome of Maker-Maker and Maker-Breaker games played on arbitrary hypergraphs are PSPACE-complete. Maker-Breaker games have earlier been shown PSPACE-complete by Schaefer (1978); we give a simpler proof and show a reduction from Maker-Maker games to Maker-Breaker games.

Available as PostScript, PDF, DVI.


Last modified: 2004-09-14 by webmaster.