## 3 CNF Formulae Evaluation  
In this section, we construct an \(\mathrm{EVAL}_{\phi}\) gadget for evaluating the truth value of a CNF formula \(\phi\) by inputting a given truth-value assignment \(a\). It has one entrance \(IN\) and two exits \(OUT_{\mathrm{FALSE}}\) and \(OUT_{\mathrm{TURE}}\). The ant entering at \(IN\) is routed to exit at \(OUT_{\mathrm{FALSE}}\) (\(OUT_{\mathrm{TRUE}}\)) if \(\phi(a)\) is FALSE (TRUE). Let \(\mathrm{POS}=\{x_{1},\ldots,x_{n}\}\) and \(\mathrm{NEG}=\{-x_{1},\ldots,\ -x_{n}\}\). Let \(y_{i,j}\in\mathrm{POS}\ \bigcup\mathrm{NEG}\) be the \(j\)th literal in the \(i\)th term of \(\phi(x_{1},\ldots x_{n})\), where \(1\leq i\leq m\) and \(1\leq j\leq k_{i}\). These literals \(y_{i,j}\) are implemented in \(\mathrm{EVAL}_{\phi}\) by S&P gadgets, named S&P\({}_{i,j}\). Then, draw PATHs between S&P\({}_{i,j}\) in the following manner to define an evaluator \(\mathrm{EVAL}_{\phi}\) of \(\phi\colon IN\to IN\) of S&P\({}_{1,1}\) (see Figure 11-1). When \(y_{i,j}\in\mathrm{POS}\ (\mathrm{NEG})\), \(OUT_{\mathrm{OFF}}\) (\(OUT_{\mathrm{ON}}\)) of S&P\({}_{i,j}\to IN\) of S&P\({}_{i,j}\) (see Figure 11-2). When \(y_{i,\ k_{i}}\in\mathrm{POS}(\mathrm{NEG})\), \(OUT_{\mathrm{OFF}}\) (\(OUT_{\mathrm{ON}}\)) of S&P\({}_{i,\ k_{i}}\to OUT_{\mathrm{FALSE}}\) (see Figure 11-3). When \(y_{m,j}\in\mathrm{POS}\ (\mathrm{NEG}\ )\), \(OUT_{\mathrm{ON}}\ (\ OUT_{\mathrm{OFF}}\ )\) of S&P\({}_{m,j}\to OUT_{\mathrm{TRUE}}\) (see Figure 11-4). For each \(x_{k}\in\mathrm{POS}\), \(\mathrm{EVAL}_{\phi}\) has an entrance \(I_{x_{k}}\) and an exit \(O_{x_{k}}\) such that the ant entering at \(I_{x_{l}}\) switches the coloring states of all S&P gadgets corresponding to the literals \(y_{i,j}\in\{x_{k},\ -x_{k}\}\) from \(OFF\) to \(ON\), and exits at \(O_{x_{l}}\). Figure 11-5 is drawing such PATHs, where the ports \(I_{x_{1}}\), \(O_{x_{1}}\), \(I_{x_{2}}\), \(O_{x_{2}}\),..., \(I_{x_{n}}\), \(O_{x_{n}}\) should be placed in this order for further development in the next section. Suppose that the coloring of the composing gadgets of \(\mathrm{EVAL}_{\phi}\) are all initialized. For every \(a\in\{\mathrm{FALSE},\mathrm{TRUE}\}^{n}\), we denote by \(INIT_{a}\) the coloring of \(\mathrm{EVAL}_{\phi}\) after taking the walking courses  
Figure 10: CROSS. **Lemma 1. ** If the coloring of \(\mathrm{EVAL}_{\mathbf{\phi}}\) is \(\mathrm{INIT}_{\mathrm{a}}\) and \(\mathbf{\phi}\)(a) = FALSE (TRUE), then the ant entering at \(IN\) exits at \(OUT_{\mathrm{FALSE}}\) (\(OUT_{\mathrm{TRUE}}\)). **Proof. ** First, suppose that \(\phi(a)=\mathrm{FALSE}\). We can assume that the \(\ell\)th term of \(\mathbf{\phi}\) is FALSE and the \(i\)th term of \(\mathbf{\phi}\) is TRUE for every \(1\leq i<l\). So, we can assume that for every \(1\leq j\leq k_{\ell}\), if \(y_{\ell,j}\in\mathrm{POS}\) ( NEG ) then S&P\({}_{\ell,j}\) is \(OFF\) ( \(ON\)), and for every \(1\leq i<l\) there exits \(1\leq j_{i}\leq k_{i}\) such that if \(y_{i,j_{i}}\in\mathrm{POS}\) (NEG) then S&P\({}_{i,j_{i}}\) is \(ON\)(\(OFF\)); in addition, for every \(1\leq j<j_{i}\), if \(y_{i,j_{i}}\in\mathrm{POS}\) (NEG) then S&P\({}_{i,j}\) is \(OFF\) (\(ON\)). Given these colorings of the S&Ps, the ant walks from \(IN\) to \(OUT_{\mathrm{FALSE}}\) in the following way: \(IN\to IN\) of S&P\({}_{1,1}\); \(IN\) of S&P\({}_{i,j}\to OUT_{OFF}\) (\(OUT_{ON}\)) of S&P\({}_{i,j_{i}}\to IN\) of S&P\({}_{i,j_{i}+1}\); \(IN\) of S&P\({}_{i,j_{i}}\to OUT_{ON}\) (\(OUT_{OFF}\)) of S&P\({}_{i,j_{i}}\to IN\) of S&P\({}_{i+1,1}\); \(IN\) of S&P\({}_{i,j_{i}}\to IN\) of S&P\({}_{i+1,1}\); \(IN\) of S&P\({}_{\ell,j}\to OUT_{OFF}\) (\(OUT_{ON}\)) of S&P\({}_{\ell,j}\to IN\) of S&P\({}_{\ell,j+1}\); \(IN\) of S&P\({}_{\ell,k_{\ell}}\to OUT_{OFF}\). Figure 11-6 illustrates this walking course by a thick line when \(\mathbf{\phi}=(x_{1}\vee-x_{2})\wedge(-x_{1}\lor x_{2})\) and \((a_{1},a_{2})=(\mathrm{TRUE},\mathrm{FALSE})\), where the gadgets have passed through, shown by the thick line, have turned to used coloring states, while the other gadgets still remain in their initial coloring.