# On Computational Hardness of Multidimensional Subtraction Games +
## 1 Introduction  
The algorithmic complexity of solving combinatorial games is an important part of algorithmic game theory. Some famous games can be solved efficiently. For example, the ancient game of nim was solved by [PERSON] in [1]. A position \(x\) of nim is determined by \(n\) heaps of pebbles. It can be considered to be a \(n\)-dimensional integer vector. By one move it is allowed to reduce (strictly) exactly one heap. Two players move alternately. One who is out of moves loses. In fact, in his paper [PERSON] obtained an explicit formula for the Sprague-Grundy (SG) function of the disjunctive compound (or, for brevity, the sum) of impartial games. Informally, the SG function is a homomorphism of an impartial game to nim with one heap. In particular, \(SG(x)>0\) and \(SG(x)=0\) indicate that the player who moves at the position \(x\) and, respectively, the opponent has a winning strategy; such positions are called N- and P-positions. See Section 2.1 and [2; 3; 4] for more details. It is important for our purposes that the formula for the SG function of nim can be computed efficiently even if the sizes of the heaps are given in binary notation. Similar efficient solutions were found for several versions and/or generalizations of nim: [PERSON]'s nim [5; 6], [PERSON]'s nim [6; 7], nim\((a,b)\) game [8], [PERSON]'s \((n,k)\)-nim with \(k=n-1\)[9; 10; 11], and the exact \((n,k)\)-nim with \(2k\geq n\)[11; 12]. In all these versions it is allowed to reduce by one move several heaps, not necessarily only one. Specifying the rules of choosing heaps and the numbers of pebbles that can be taken, one gets different versions of nim. For example, in the exact (resp., Moore) \((n,k)\)-nim a player by one move reduces exactly (resp., at most) \(k\) from \(n\) heaps, strictly but otherwise arbitrarily, where \(n\) and \(k\) are fixed integer parameters such that \(0<k<n\). Another way to change the rules is to restrict moves to _slow_ ones. A move is called _slow_ if at most one pebble is taken from each heap. The Moore and exact _slow_\((n,k)\)-nim were introduced in [13; 14]. In the study of the exact slow \((n,k)\)-nim explicit and efficiently computable formulas for the SG function were obtained for \((n,k)=(3,2)\)[13] and for \((n,k)=(4,2)\)[14]. However, for larger values of \(k\), no explicit formula for the SG function of the exact or Moore slow \((n,k)\)-nim is known. Moreover, numerical experiments show that even P-positions look rather chaotic. Is it possible that there is no efficient algorithm solving these variants of nim? Right now, we have no answer to this question and even no clue. As for hardness results, we could mention numerous examples of **PSPACE**-complete combinatorial games (see, e.g., [15; 16]) and also **NP**-hardness of hypergraph nim for some classes of hypergraphs [17; 18]. The game _hypergraph nim_, \(\mathrm{NIM}_{\mathcal{H}}\), is specified by a hypergraph \(\mathcal{H}\subseteq 2^{[n]}\setminus\{\varnothing\}\) on the ground set \([n]=\{1,\ldots,n\}\). It is played as follows. By one move a player chooses an edge \(H\in\mathcal{H}\) and strictly reduces all heaps of \(H\). The games of standard (not slow) exact and [PERSON]'s nim considered above provide examples of the hypergraph nim. The _height_\(h(x)=h_{\mathcal{H}}(x)\) of a position \(x=(x_{1},\ldots,x_{n})\) of \(\mathrm{NIM}_{\mathcal{H}}\) is the maximum number of successive moves that players can make beginning in \(x\). (Clearly, they can restrict themselves by their slow moves.) A hypergraph \(\mathcal{H}\) is called _intersecting_ if \(H^{\prime}\cap H^{\prime\prime}\
eq\varnothing\) for any two edges \(H^{\prime}\), \(H^{\prime\prime}\in\mathcal{H}\). It was proved in [17; 18] that for any intersecting hypergraph \(\mathcal{H}\), its height and SG function are equal. In [17] it was proved that computing \(h_{\mathcal{H}}(x)\) is **NP**-hard already for the intersecting hypergraphs with edges of size at most 4. Thus, **NP**-hardness of computing the SG function for such family of hypergraphs follows from these two statements.