# On Computational Hardness of Multidimensional Subtraction Games +
## 2 Concepts and Results
### Subtraction Games and Modular Games  
Now we introduce the class FDG of subtraction games. Subtraction games generalize naturally all versions of nim mentioned above. Please note that a position in a version of nim with \(d\) heaps is specified by a \(d\)-dimensional vector \(x=(x_{1},\dots,x_{d})\) with nonnegative integer coordinates which are just the numbers of pebbles in a heap. A move in the game decreases some coordinates of this vector. Thus, possible moves are specified by a set \(\mathcal{D}(x)\subseteq\mathbb{N}^{d}\) of \(d\)-dimensional vectors with nonnegative integer coordinates (the _difference set_). A move from \(x\) to \(y\) is possible if \(x-y\in\mathcal{D}(x)\). **Example 1**: _Suppose that \(x=(x_{1},\dots,x_{n})\) is a position in the exact slow \((n,k)\)-nim introduced in Section 1. Any legal move in this position should decrease exactly \(k\) values of the coordinates by \(1\). Therefore \(\mathcal{D}(x)\) is the set of \(d\)-dimensional \((0,1)\)-vectors with exactly \(k\) ones, for any \(x\)._  
A subtraction game is defined by similar rules. There are two important differences. In a subtraction game the difference set \(\mathcal{D}\) is the same for all positions. In a general subtraction game \(\mathcal{D}\) may contain integer vectors with negative coordinates. It terms of heaps and pebbles it means that a player is allowed to add pebbles to heaps. To avoid infinite plays, we require that the total number of pebbles should be strictly reduced by each move. It is equivalent to the following condition on coordinates of difference vectors:  
\[\sum_{i=1}^{d}a_{i}>0 \tag{3}\]  
for any difference vector \(a\in D\). Finally, a game from the class FDG is defined by a _finite_ difference set \(\mathcal{D}\) of \(d\)-dimensional vectors satisfying (3). In particular, the exact slow \((n,k)\)-nim belongs to FDG. **Example 2**. : _Let \(\mathcal{D}=\{(2,-1),(-1,2)\}\). Then possible moves from position \((3,3)\) are to positions \((1,4)\) and \((4,1)\). It is an easy exercise to compute the value of the position: \(p(3,3)=0\), i.e., it is a P-position._  
Due to (3), any play of a FDG starting at a position \((x_{1},\ldots,x_{d})\) includes only positions with smaller sums of the coordinates. Therefore, computing the value of \((x_{1},\ldots,x_{d})\) by the basic recurrence relation (2) requires the values at most  
\[\binom{M+d}{d}=O(M^{d})\]  
positions, where \(M=\sum_{i}x_{i}\). Therefore, due to the kernel construction algorithm mentioned above, solving FDG belongs to the class **EXP** if the \(x_{i}\) are presented in binary notation. This exponential bound on the complexity of solving FDG holds in the case when the difference set is a part of the input. It is easy to show that in this case solving FDG is **PSPACE**-hard. For this purpose, we reduce solving the game called NODE KAYLES to solving a FDG. Recall the rules of NODE KAYLES. It is played on a graph \(G\). At each move a player puts a pebble on an unoccupied vertex of \(G\) that is non-adjacent to any occupied vertex. As usual, the player unable to make a move loses. **Proposition 1**. : _Solving NODE KAYLES is polynomially reducible to solving FDG._  
Proof. : Let \(G=(V,E)\) be a graph of NODE KAYLES. Construct a \(|E|\)-dimensional subtraction game with the difference set \(A_{G}\) indexed by the vertices of \(G\): \(D=\{a^{(v)}:v\in V\}\), where  
\[a^{(v)}_{c}= \begin{cases}1,&\text{the vertex $v$ is incident to the edge $e$,}\\ 0,&\text{otherwise.}\end{cases} \]  
We assume in the definition that the coordinates are indexed by the edges of the graph \(G\). Take the position \(1\) with all coordinates equal \(1\). We are going to prove that this position is a P-position of the FDG \(A_{G}\) iff the graph \(G\) is a P-position of NODE KAYLES. Indeed, after subtracting a vector \(a^{(v)}\), coordinates indexed by the edges incident to \(v\) are zero. It means that after this move it is impossible to subtract the vector \(a^{(v)}\) and any vector \(a^{(u)}\) such that \((u,v)\in E\).