There's a popular game, when two people each after each call cities in such a way that every next city begins with the previous one's last letter. For, example:
A: Washington
B: New Orleans
A: Syndey
B: York
A: ...
The first one who can't name anything loses. Cities cannot be repeated. It doesn't matter whether the initial city is predefined or chosen by the first player. Now the question:
The language of all lists of cities, which having based the game on, the first player wins in spite of the second's strategy — what class contains it more or less effectively? (it would be nice if the problem was complete somewhere)
I was trying to think of something myself but no success yet. For now I feel that it is not in NP, since I can't possibly imagine any kind of certificate which would let quickly check it's validity. It should be in PSPACE anyway, because it is finite. But I have no idea about any completeness, non-inclusion or just hardness.
I'd be happy if somebody could give me a hand about what to do or just hint at some complete language(s) which are similar to my problem. The problem is, I know too few (N)EXP- and PSPACE-complete languages, and have very little experience in working with these sets.
Thanks in advance.
Consider the game played with a specified finite list $C$ of cities, where $|C|=N$. Then $C = \bigcup_{i,j \in \{``a"\ldots``z"\}} C_{ij}$ where $C_{ij}$ is the subset of $C$ consisting of cities whose name starts with $i$ and ends with $j$. A state of the game conists of nonnegative integers $n_{ij}$ (the number of cities in $C_{ij}$ that have not yet been named) plus the last letter of the last city named (or 0 if this is the first turn). Thus there are less than $27 N^{26^2}$ possible states of the game. Dynamic programming can determine in polynomial time which states are wins for which player.