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

Authors

  • Jesper Makholm Byskov

DOI:

https://doi.org/10.7146/brics.v11i14.21839

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.

Downloads

Published

2004-08-11

How to Cite

Byskov, J. M. (2004). Maker-Maker and Maker-Breaker Games are PSPACE-Complete. BRICS Report Series, 11(14). https://doi.org/10.7146/brics.v11i14.21839

Issue

No. 14 (2004): RS-14 Maker-Maker and Maker-Breaker Games are PSPACE-Complete

Section

Articles

License

Creative Commons License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.