Let $\mathfrak{G}$ be the class of all finite directed and undirected graphs. Let $A,B\subseteq \mathfrak{G} $, $A$ and $B$ are closed under graph isomorphisms, and $A \cap B = \varnothing$. Consider the following two player game. On the graph $G \in \mathfrak{G} $ with the starting vertex $u$, play as follows: the first player presents $x_1 \subseteq V(G)$ such that $\forall v\in x_1\; uv\in E(G)$. Then the players in turn present the sets of vertices, so that for any different $x_i$ and $x_j$ satisfy $x_i \cap x_j = \varnothing$, and $\forall v\in x_k \; \exists w\in x_{k-1} : wv\in E(G)$.
Conditions for victory and defeat (checked on each turn in the order of the following list):
- If on turn $n$ there exists $k$ such that the induced subgraph $\bigcup_\limits{i=k}^n x_i$ contains a subgraph $H$ isomorphic to a graph from $A$, then the player who made the move $n$ wins.
- If on turn $n$ there exists $k$ such that the induced subgraph $\bigcup_\limits{i=k}^n x_i$ contains a subgraph $H$ isomorphic to a graph from $B$, then the player who made the move $n$ loses.
- If after some move the player cannot make a move, then he loses.
For example, if condition 2 is satisfied on the last move, then the player who made this move loses, because condition 2 is checked earlier than condition 3. Or if after the player's move a graph appears containing subgraphs from both $A$ and $B$, then he wins, because condition 1 is checked before condition 2. Let call this game $A-B$ game.
Consider the following language:
$$A-B-NG:=\{(G,u): \text{there is a winning strategy for the first player in $A-B$ game} \}$$
The complexity of this language depends on the classes we are considering. For example, if $pt$ is one-vertex graph, then $\{pt\}-B-NG \in \mathrm{DTIME(1)}$, because condition 1 is satisfied for all non-empty graphs. But $GG\leq_p \varnothing – \varnothing – NG$, therefore $ \varnothing – \varnothing – NG \in \mathrm{PSPACE-complete} $ (because $\varnothing – \varnothing – NG \leq_p GG $ ). Is it possible to choose $A$,$B$ so that $A-B-NG$ will have an even worse nesting, that is, it will lie in a class strictly above $ \mathrm{PSPACE} $, or containing $ \mathrm{PSPACE} $ ?
Best Answer
No, it is not possible to go above PSPACE, because all positional games with an exponentially large game tree are in PSPACE; you can just check all the options. And the game when $A=B=\emptyset$ is indeed PSPACE-hard, I've found a gadget to reduce the original Generalized Geography to it.
Update: Some of my students found a simpler gadget: Just replace each directed edge by a path of length 3. If anytime someone picks more than one vertices, then they practically yield their option to pick the next vertex to their opponent.