1
$\begingroup$

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):

  1. 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.
  2. 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.
  3. 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} $ ?

$\endgroup$
2
  • 1
    $\begingroup$ Are $A$ and $B$ just a finite collection of graphs? If not, how are they presented? I don't see how to reduce Generalized Geography to your game, as you allow players to pick sets of vertices rather than a single vertex. $\endgroup$
    – domotorp
    Oct 15 '21 at 15:31
  • $\begingroup$ I think we should accept that the Turing machine has an oracle for both sets. You are absolutely right, I have not indicated the correct reduction from $GG$ to $\varnothing - \varnothing- NG$ :(. I assume that it exists and I will think about how to build it. $\endgroup$
    – Ben Tom
    Oct 15 '21 at 18:40
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you explain why the game tree is exponentially large? It is not very clear to me. $\endgroup$
    – Ben Tom
    Oct 15 '21 at 20:18
  • $\begingroup$ You just need to store which vertices have been claimed, plus the last claimed vertex set. This is $3^n$ bits. $\endgroup$
    – domotorp
    Oct 15 '21 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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