In computational complexity theory, generalized geography is a well-known PSPACE-complete problem.
Geography is a children's game, where players take turns naming cities from anywhere in the world.
The game begins with an arbitrary starting city and ends when a player loses because he or she is unable to continue.
To visualize the game, a directed graph can be constructed whose nodes are each cities of the world.
The problem of determining which player has a winning strategy in a generalized geography game is PSPACE-complete.
Let GG = { ⟨G, b⟩ | P1 has a winning strategy for the generalized geography game played on graph G starting at node b }; to show that GG ∈ PSPACE, we present a polynomial-space recursive algorithm determining which player has a winning strategy.
The space consumed by the recursion stack is polynomial because each level of recursion adds a single node to the stack, and there are at most n levels, where n is the number of nodes in G. This is essentially equivalent to a depth-first search.
In brief, an instance of the FORMULA-GAME problem consists of a quantified Boolean formula φ = ∃x1 ∀x2 ∃x3 ...Qxk(ψ) where Q is either ∃ or ∀.
The game is played by two players, Pa and Pe, who alternate choosing values for successive xi.
In this proof, we assume that the quantifier list starts and ends with the existential qualifier, ∃, for simplicity.
Note that any expression can be converted to this form by adding dummy variables that do not appear in ψ.
By constructing a graph G like the one shown above, we will show any instance of FORMULA-GAME can be reduced to an instance of Generalized Geography, where the optimal strategy for P1 is equivalent to that of Pe, and the optimal strategy for P2 is equivalent to that of Pa.
The left vertical chain of nodes is designed to mimic the procedure of choosing values for variables in FORMULA-GAME.
Since all the literals in the clause are false, they do not connect to previously visited nodes in the left vertical chain.
This allows P2 to follow the connection to the corresponding node in a diamond of the left chain and select it.
This is not possible in general, but is always possible for the graph constructed from a FORMULA-GAME instance; for example we could have only the edges from clause vertices involved in crossings.
[2] One may also consider playing either Geography game on an undirected graph (that is, the edges can be traversed in both directions).
If the graph is bipartite, then Undirected Edge Geography is solvable in polynomial time.