|
Maker-Maker and Maker-Breaker Games are PSPACE-Complete
Jesper Makholm Byskov August 2004 |
Abstract:
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. |