# Generalized Geography with repetitions

Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to move wins.

GG = { : G is a directed graph, b is a node in G, and the next player to play has a winning strategy for generalized geography from start node b, i.e., there are moves for the next player to win no matter how opponent plays }

This problem is well-known to be in PSPACE and EXPTIME-hard. My question is: If we allow repetitions in GG, it still belongs to EXPTIME-hard?

• GG is PSPACE-complete, if it was EXPTIME-hard and in PSPACE, then PSPACE would equal EXPTIME.
– domotorp
Mar 21, 2014 at 13:13
• What do you mean with repetitions, do you mean that a node can be traversed multiple times? If yes, are players allowed to undo a move going back from the last edge picked by the opponent? Is the number of the repetitions bounded and given as input?
– Vor
Mar 21, 2014 at 14:02
• This problem is PSPACE complete (i.e. in PSPACE and PSPACE-hard), not EXPTIME-hard. Otherwise it would imply EXPTIME=PSPACE. Mar 21, 2014 at 16:16
• Also, what do you mean by "allowing repetitions"? If you allow repetitions, then there are infinite plays in the game, and the winning condition is not well-defined. And please don't cross-post without reference (cstheory.stackexchange.com/questions/21657/…) Mar 21, 2014 at 16:17