6-Uniform Maker-Breaker Game Is PSPACE-Complete
Lutfar Rahman, Thomas W. Watson · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2021
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.