# On Computational Hardness of Multidimensional Subtraction Games +
## 8 Discussion  
Our hardness result drastically contrasts with the results on slow nim in [13; 14]. For these games, a rather simple formula was obtained for the SG function. So, these games are solved efficiently. Slow versions of nim can be considered to be FDG, see Example 1. The difference sets for these games consist of \((0,1)\)-vectors. A more general subclass of FDG is formed by games whose difference vectors are nonnegative. In other words, players are not allowed to add pebbles to heaps. In our proof we use the construction by [PERSON]. The negative coordinates of difference vectors are essential in it. We see no way to maintain a counter modulo \(N\) without such vectors in the difference set. Moreover, we believe that the existence of difference vectors with negative coordinates is essential for both hardness results: ours and the undecidability result from [19]. **Conjecture 1**. : _For any FDG game such that \(a_{i}\geq 0\) for each \((a_{1},\dots,a_{d})\in\mathcal{D}\), there exists a polynomial algorithm solving the game, i.e., \(\mathcal{P}(\mathcal{D})\in\mathbf{P}\)._  
To the best of our knowledge, P-positions of all efficiently solved FDG form semilinear sets. Recall that a _semilinear set_ is a set of vectors from \(\mathbb{N}^{d}\) that can be expressed in Presburger arithmetic; see, e.g., [26]. Presburger arithmetic admits quantifier elimination. Therefore, a semilinear set can be expressed as a finite union of solutions of systems of linear inequalities and equations modulo some integer (fixed for the set). **Conjecture 2**. : _For any FDG game such that \(a_{i}\geq 0\) for each \((a_{1},\dots,a_{d})\in\mathcal{D}\), the set of P-positions is semilinear._  
It is well-known that evaluating a formula in Presburger arithmetic is a very hard problem. The first doubly exponential time bound for this problem was established by [PERSON] and [PERSON] [27]. [PERSON] proved that the problem requires doubly exponential space [28]. However, these hardness results are irrelevant for our needs. In solving FDG games we deal with sets of dimension \(O(1)\) and we may hardwire the description of the set of P-positions in an algorithm solving the game. Verifying a linear inequality takes a polynomial time as well as verifying an equation modulo some integer. Thus, any semilinear set of dimension \(O(1)\) can be recognized by a polynomial time algorithm. Therefore Conjecture 2 implies Conjecture 1. Conjecture 2 also implies that the equivalence problem for FDG with nonnegative difference vectors is decidable, since Presburger arithmetic is decidable. Indeed, by Post'stheorem a set is decidable if it is enumerable and co-enumerable. The set \(E=\{(\mathcal{D}_{1},\mathcal{D}_{2}):\mathcal{P}(\mathcal{D}_{1})=\mathcal{P}( \mathcal{D}_{2})\}\) is trivially co-enumerable, since it is decidable to check whether \(x\in\mathcal{P}(\mathcal{D}_{1})\setminus\mathcal{P}(\mathcal{D}_{2})\) applying the kernel construction algorithm. On the other hand, the set \(\{((\mathcal{S}),\mathcal{D}_{1},\mathcal{D}_{2}):S=\mathcal{P}(\mathcal{D}_{ 1})=\mathcal{P}(\mathcal{D}_{2})\}\), where \(\langle S\rangle\) is a description of a semilinear set \(S\), is decidable: the statement \(S=\mathcal{P}(\mathcal{D})\) can be expressed in Presburger arithmetic. Therefore set \(E\) is enumerable. Why do we believe in Conjecture 2 despite results from [19] and ours? It seems that some inductive arguments can be applied in the case of nonnegative difference vectors. Please note that Conjecture 2 holds for a 1-dimensional FDG [22]. If a coordinate becomes zero it remains zero during the rest of the game (if all difference vectors are nonnegative). Thus, it might be possible to prove the implication: if \"boundary conditions\" are semilinear then the solution of a game is also semilinear. (After the paper was submitted, [PERSON] pointed out that this claim is false for _arbitrary_ semilinear boundary conditions. However, his arguments cannot be applied to boundary conditions produced by games). The above observations show a way to Conjecture 2.