# On Computational Hardness of Multidimensional Subtraction Games +
## 7 Proof of the Main Theorem  
As a hard language, we use the language of the bounded halting problem  
\[L=\{(\langle M\rangle,x,0^{k}):M\text{ accepts $x$ after at most $2^{k}$ steps}\},\]  
which is obviously **EXP**-complete. The following proposition is an easy corollary of the time hierarchy theorem [25]. Proposition 5: \(L\
otin\mathbf{DTIME}(2^{n/2})\)_, where \(n\) is the input size._  
Proof. : Take an arbitrary language \(L^{\prime}\in\mathbf{DTIME}(2^{2n})\), where \(n\) is the input size. Let \(M^{\prime}\) be a Turing machine recognizing \(L^{\prime}\) in time \(2^{2n+c}\), where \(c\) is a suitable constant. The function  
\[x\mapsto(\langle M^{\prime}\rangle,x,0^{2|x|+c})\]  
provides a polynomial reduction of \(L^{\prime}\) to \(L\). Let us suppose for the sake of contradiction that \(L\) is recognized by a Turing machine \(M\) in time \(C\cdot 2^{n/2}\), where \(n\) is the input size. Consider an algorithm to decide \(x\in L^{\prime}\):  
1. Compute \((\langle M^{\prime}\rangle,x,0^{2|x|+c})\) (requires \(\operatorname{poly}(|x|)\) time). 2. Run \(M\) on the input \((\langle M^{\prime}\rangle,x,0^{2|x|+c})\) (requires \(O(2^{3|x|/2})\) time). The total running time of this algorithm is \(O(2^{1.5n})\). Thus, \(\mathbf{DTIME}(2^{2n})\subseteq\mathbf{DTIME}(2^{15n})\). It contradicts the time hierarchy theorem. Using universal Turing machine and counters it is easy to get an upper bound of the algorithmic complexity of \(L\). Proposition 6: \(L\in\mathbf{DTIME}(n^{2}\cdot 2^{n})\)_, where \(n\) is the input size._  
Proof. : To verify \((\langle M\rangle,x,0^{k})\in L\) one needs to implement a universal Turing machine and a counter of size \(k\). To speed up computation, the description \(\langle M\rangle\) and the counter are shifting along the tape. Shifting by 1 requires time \(O(|\langle M\rangle|+k))\) as well as updating the counter. To apply the transition function of \(M\), it suffices to align the corresponding entry of the transition function with the current position of the head. Thus, to simulate a step of computation made by \(M\) on the input \(x\), one needs \(O((|\langle M\rangle|+k)^{2})=O(n^{2})\) time, where \(n\) is the input size. The total number of simulation steps is at most \(2^{k}\leq 2^{n}\). Based on Proposition 6, we fix a Turing machine \(M\) recognizing \(L\) such that for some constant \(C\) the machine \(M\) makes at most \(T(n)=C\cdot(n+1)^{2}\cdot 2^{n}\) steps on inputs of size \(n\)For machine \(M\) apply the construction from Section 6 and Proposition 4 to construct the machine \(U\). Then convert \(U\) into 2 CA \(C_{U}^{(2)}\) as described in Section 5. We put an additional requirement on bijection \(\pi\), namely \(\pi(0,\text{yes}))=L-1\). It locates the result of computation of \(M\) in the third bit of the encoding of the result block. More specifically, this bit is \(0\) iff \(M\) accepts the corresponding input. Finally, construct \(O(1)\)-dimensional FDG \(\mathcal{D}_{C}\) as it described in Section 4. The dimension \(2N+2\) of the game is determined by machine \(M\). By Corollary 1, the symbol \(c_{t}(u)\) on the tape of \(C_{U}^{(2)}\) equals the value of position \((Nt+u,Nt-u,0,0,\ldots,0,1)\) of the game. Define the function \(\rho\colon w\mapsto(Nt+u,Nt-u,0,0,\ldots,0,1)\) as follows. Set \(t=2^{4n}\), where \(n\) is the size of \(w\). Set \(u\) be the position of the bit carrying the result of computation of \(M\) on input \(w\) in the image of the resulting block of the zone \(k\) corresponding to the input \(w\). **Proposition 7**. : (i) There exists a polynomial reduction of the language \(L\) to the language \(\mathcal{P}(\mathcal{D})\) based on the function \(\rho\colon w\mapsto(Nt+u,Nt-u,0,0,\ldots,0,1)\)__  
Proof. : The reduction is defined by the function  
\[\rho\colon w\mapsto(Nt+u,Nt-u,0,0,\ldots,0,1)\]  
for sufficiently large inputs (taking into account Proposition 4). For the rest of inputs (there are \(O(1)\) of them), the reduction is defined in an arbitrary way preserving correctness.