2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ GG is PSPACE-complete, if it was EXPTIME-hard and in PSPACE, then PSPACE would equal EXPTIME. $\endgroup$
    – domotorp
    Mar 21, 2014 at 13:13
  • $\begingroup$ 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? $\endgroup$
    – Vor
    Mar 21, 2014 at 14:02
  • $\begingroup$ This problem is PSPACE complete (i.e. in PSPACE and PSPACE-hard), not EXPTIME-hard. Otherwise it would imply EXPTIME=PSPACE. $\endgroup$
    – Shaull
    Mar 21, 2014 at 16:16
  • 3
    $\begingroup$ 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/…) $\endgroup$
    – Shaull
    Mar 21, 2014 at 16:17

1 Answer 1

Reset to default
3
$\begingroup$

If repetitions are allowed, the problem is in P, as the (immediate) losing nodes are the ones with no outgoing edges, first find these, then declare the nodes winning from which you can reach such a node, if you can reach only winning ones, its a losing node, and so on, rest are drawing.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.