Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-097 | 30th June 2020 02:52

6-Uniform Maker-Breaker Game Is PSPACE-Complete

RSS-Feed




TR20-097
Authors: Md Lutfar Rahman, Thomas Watson
Publication: 30th June 2020 18:23
Downloads: 775
Keywords: 


Abstract:

In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains PSPACE-complete even when every set has size 6.



ISSN 1433-8092 | Imprint