  We settle two long-standing complexity-theoretical questions-open since 1981
and 1993-in combinatorial game theory (CGT).
  We prove that the Grundy value (a.k.a. nim-value, or nimber) of Undirected
Geography is PSPACE-complete to compute. This exhibits a stark contrast with a
result from 1993 that Undirected Geography is polynomial-time solvable. By
distilling to a simple reduction, our proof further establishes a dichotomy
theorem, providing a "phase transition to intractability" in Grundy-value
computation, sharply characterized by a maximum degree of four: The Grundy
value of Undirected Geography over any degree-three graph is polynomial-time
computable, but over degree-four graphs-even when planar and bipartite-is
PSPACE-hard. Additionally, we show, for the first time, how to construct
Undirected Geography instances with Grundy value $\ast n$ and size polynomial
in n.
  We strengthen a result from 1981 showing that sums of tractable partisan
games are PSPACE-complete in two fundamental ways. First, since Undirected
Geography is an impartial ruleset, we extend the hardness of sums to impartial
games, a strict subset of partisan. Second, the 1981 construction is not built
from a natural ruleset, instead using a long sum of tailored short-depth game
positions. We use the sum of two Undirected Geography positions to create our
hard instances. Our result also has computational implications to
Sprague-Grundy Theory (1930s) which shows that the Grundy value of the
disjunctive sum of any two impartial games can be computed-in polynomial
time-from their Grundy values. In contrast, we prove that assuming PSPACE
$\neq$ P, there is no general polynomial-time method to summarize two
polynomial-time solvable impartial games to efficiently solve their disjunctive
sum.
