Kyle Burke

Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography

2022

We settle two long-standing complexity-theoretical questions—open since 1981 and 1993—in combinatorial game theory (CGT). We prove that the Grundy value of Undirected Geography is PSPACE-complete to compute. This exhibits a stark contrast with a result …