The back-and-forth complexity tradeoff conjecture

For a countable structure $\mathcal{M}$, write $\{\mathcal{N}:\mathcal{N}\geq_n\mathcal{M}\}$ and $\{\mathcal{N}:\mathcal{N}\leq_n\mathcal{M}\}$ for the classes of countable structures related to $\mathcal{M}$ by the corresponding back-and-forth relations. Here $\Pi^0_k$ and $\Sigma^0_k$ denote the effective Borel complexity classes, and an index set is $m$-complete when it is many-one complete.

Back-and-forth complexity tradeoff conjecture. For the indicated parity conditions, there are structures with the following exact complexities:

1. For even $n\geq 2$, there is a structure $\mathcal{M}$ such that

$$\{\mathcal{N}:\mathcal{N}\geq_n\mathcal{M}\}$$

is $\Pi^0_{2n}$ but not $\Sigma^0_{2n}$.

2. For odd $n\geq 3$, there is a structure $\mathcal{M}$ such that

$$\{\mathcal{N}:\mathcal{N}\geq_n\mathcal{M}\}$$

is $\Pi^0_{2n-1}$ but not $\Pi^0_{2n-1}$.

3. For even $n\geq 2$, there is a structure $\mathcal{M}$ such that

$$\{\mathcal{N}:\mathcal{N}\leq_n\mathcal{M}\}$$

is $\Pi^0_{2n-1}$ but not $\Sigma^0_{2n-1}$.

4. For odd $n\geq 3$, there is a structure $\mathcal{M}$ such that

$$\{\mathcal{N}:\mathcal{N}\leq_n\mathcal{M}\}$$

is $\Pi^0_{2n}$ but not $\Sigma^0_{2n}$.

Moreover, each assertion is witnessed by an index-set result for countable structures; for example, in (1), the index set $\{i:\mathcal{N}_i\leq_n\mathcal{M}\}$ is $\Pi^0_{2n}$ $m$-complete.

The conjecture formalizes the claimed tradeoff between lower quantifier complexity and non-effectivity in the formulas defining back-and-forth relations. The source does not provide a proof or resolution, and notes that the parity distinction comes from the base case of the back-and-forth game.