Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-185 | 6th December 2019 07:27

Strategy-Stealing is Non-Constructive

RSS-Feed




TR19-185
Authors: Greg Bodwin, Ofer Grossman
Publication: 29th December 2019 07:25
Downloads: 82
Keywords: 


Abstract:

In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing.
This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing that one exists?
We prove that this problem is PSPACE-Complete already for Minimum Poset Games and Symmetric Maker-Maker Games, which are simple classes of games that capture two of the main types of strategy-stealing arguments in the current literature.



ISSN 1433-8092 | Imprint