# Hardness of Approximation for Langton's Ant on a Twisted Torus
## 1 Introduction
### A Proof Outline  
Figure 4 reduces QCNF to [PERSON]'s ant problem of distinguishment between \((\rho_{2}(\theta),\xi_{2}(\theta))=(0,0)\) and \((1,\frac{208}{11})\). It maps a given QCNF instance \(\Phi=\{\Phi_{n}\}\), say \(\Phi_{n_{0}}=\forall x_{1},\exists x_{2},(x_{1}\vee\
eg x_{2})\wedge(\
eg x_{1 }\lor x_{2})\) for a sufficiently large \(n_{0}\) to encode it on \(\mathbb{Z}_{n_{0}}\times\mathbb{Z}_{n_{0}}\), to a coloring \(\theta(\Phi)=\{\theta_{n}(\Phi_{n})\}\) on microscopic field. The ant starting from the _port_ (i.e., edge) \(S\) of TURN-A gate walks along a line and gets into the \(G[\Phi]\)_chip_ (a collection of gates) at the entrance port \(I\). The ant evaluates \(\Phi\) and gets out from either the exit port F if it is FALSE or T if it is TRUE. In the former case, the ant reaches TURN-B gate. Since each TURN gate _reverses_ the ant (i.e., putting the ant on the same port in the opposite direction), it must repeat a closed-loop between TURN-A and TURN-B gates due to _time-reversibility_; the reversed ant must travel back and rewind all steps it has taken in the time-reversing order. This loop holds the ant on microscopic field and thus makes a reduction \(\Phi=\mathrm{FALSE}\Rightarrow\left(\rho_{2}(\theta(\Phi)),\xi_{2}(\theta( \Phi))\right)=(0,0)\). Similarly, the latter case induces another loop between TURN-A and TURN-C gates, passing through Hamiltonian-tour gate on the way, which drives the ant to visit almost all vertices in macroscopic field. It yields \(\Phi=\mathrm{TRUE}\Rightarrow\left(\rho_{2}(\theta(\Phi)),\xi_{2}(\theta( \Phi))\right)=(1,\frac{208}{11})\), where \(\frac{208}{11}=4/11\cdot\sqrt{2}/(\sqrt{2}/52)\). Since these TURN gates take binary states flipping at the ant's every visit, the ant travels Figure 3's Hamiltonian-tour four times until revisiting the initial configuration. Each Hamiltonian-tour consists of \((N-O(n))/11\) rounds of length-\(\sqrt{2}N\) diagonals, taking \((N-O(n))/11\cdot\sqrt{2}N/(\sqrt{2}/52)\) time since the ant's speed is \(\sqrt{2}/52\)[13]. Our previous paper [15] has already provided a coloring for the \(G[\Phi]\) chip to evaluate a QCNF formula \(\Phi\), but using _gray vertices_ at which the ant goes straight without changing the color [10]. Since it has permitted only a single gray vertex at each TURN gate and nowhere else, we are enough to exhibit only a new TURN gate with no gray vertex. However, open square lattice topology prohibits it because it tessellates the vertices of \(\mathbb{Z}\times\mathbb{Z}\) into chess-board symmetry of \(\{H,V\}\)-polarity: Every H-vertex (resp. V-vertex) permits the ant to come Horizontally (resp. Vertically) and go vertically (resp. horizontally). Even-twist torus preserves \(\{\mathrm{H},\mathrm{V}\}\)-polarity, but odd-twist torus breaks it. If the ant living in odd-twist torus travels around vertically and comes back to the initial place, it can visit the world where every vertex possesses the opposite polarity. Figure 5 realizes a TURN gate in virtue of this polarity switching phenomenon. The ant enters at the port \(S\), passing through FL (FLipper) gate, and reaching HW (HighWay) gate. The ant gets on Figure 2's highway and travels towards a \(\sqrt{2}N\) away destination place in a diagonal direction. The odd-twist torus's topology brings the ant to a new world possessing the same address but the opposite polarity. Accordingly, after getting off the highway, the ant passes through the FL gate again and gets out the TURN gate from the same port \(S\) that it has entered but in the opposite direction. Figure 4: An ant’s travel for QCNF. Figure 5: TURN. A Hamiltonian-tour gate to visit almost all vertices is easy to realize: Let the ant get on a highway at the entrance port I of top-left \(H_{2}\) in Figure 4. It brings the ant to a Hamiltonian tour along screwing diagonals of Figure 3: Each diagonal transports the ant by a horizontal and vertical distance \(N\), bringing it back to the same address but a horizontal displacement \(\pm 11\) due to the twisted torus topology.