# Problems on Finite Automata and the Exponential Time Hypothesis
## 3 The Non-Tally Case  
In the classical setting, the automata problems that we study are harder for binary (and larger) input alphabet sizes (PSPACE-complete; for instance, see [17]). Also, notice that the best-known algorithms are also slower in this case. This should be reflected in the lower bounds that we can obtain for them (under ETH), too. Let us describe a modification (and in a sense a simplification) of our reduction from 3-Coloring. Let \(G=(V,E)\) be an undirected graph. We construct an NFA \(A\) (on a ternary alphabet \(\Sigma=\{a,b,c\}\) for simplicity) as follows. \(\Sigma\) corresponds to the set of colors with which we like to label the vertices of the graph. The state set is \(\{s\}\cup(E\times V\times\Sigma)\). W.l.o.g., \(V=\{v_{1},\ldots,v_{n}\}\). For \(e=uv\) and \(x,y\in\Sigma\), we add the following transitions. \(\bullet\quad s\stackrel{{ x}}{{\longrightarrow}}(e,v_{1},y)\) if \(v_{1}\
otin\{u,v\}\) or if \((u=v_{1}\lor v=v_{1})\wedge y=x\); \(\bullet\quad(e,v_{i},y)\stackrel{{-\chi}}{{\longrightarrow}}(e,v _{i+1},y)\) (for \(i=1,\ldots,n-1\)) if \(v_{i+1}\
otin\{u,v\}\) or if \((u=v_{i+1}\lor v=v_{i+1})\wedge y=x\); \(\bullet\quad(e,v_{n},y)\stackrel{{-\chi}}{{\longrightarrow}}s\). Moreover, \(s\) is the only initial and all states are final states. If \(z=z_{1}z_{2}\cdots z_{n+1}\in L(A)\), then this corresponds to a coloring \(c:V\to\Sigma\) via \(c(v_{k})=z_{k},k=1,\ldots,n\), that is not proper. Namely, \(z\) drives the \(A\) through the states \(s\), \((e,v_{1},y)\), \((e,v_{2},y)\), \(\ldots\), \((e,v_{n},y)\), \(s\) for some \(e=v_{i}v_{j}\in E\) and some \(y\in\Sigma\). By construction, this is only possible if \(c(v_{i})=c(v_{j})=z_{i}=z_{j}=y\), establishing the claim. Conversely, if \(c:V\to\Sigma\) is a coloring that is improper, then there is an edge, say, \(e=v_{i}v_{j}\), such that \(c(v_{i})=c(v_{j})=y\) for some \(y\in\Sigma\). Then, \(z:=z_{1}z_{2}\cdots z_{n}a\in L(A)\), where \(z_{k}=c(v_{k})\), \(k=1,\ldots,n\). Namely, this \(z\) will drive \(A\) through the states \(s\), \((e,v_{1},y)\), \((e,v_{2},y)\), \(\ldots\), \((e,v_{n},y)\), \(s\). Hence, for the constructed automaton \(A\), \(L(A)\
eq\Sigma^{\bullet}\) if and only if there is some proper coloring \(c:V\to\Sigma\) of \(G\). For such a proper coloring \(c,z:=z_{1}z_{2}\cdots z_{n}a\
otin L(A)\), where \(z_{k}=c(v_{k})\), \(k=1,\ldots,n\). As \(m\geqslant n\), the number of states of \(A\) is \(O(m^{2})\). So, we can conclude a lower bound of the form \(O^{\bullet}\left(2^{o(\sqrt{q})}\right)\). We are now further modifying this construction idea to obtain the following tight bound. Theorem 3.1: _Assuming ETH, there is no algorithm for solving Universality for \(q\)-state NFAs with binary input alphabets that runs in time \(O^{\bullet}\left(2^{o(q)}\right)\)._  
Proof. : As we can encode the union of all the NFAs above more succinct we get a better bound. Let \(G=(V,E)\) be an undirected graph, and \(V=\{v_{1},\ldots,v_{n}\}\) as above. Let \(\Sigma=\{a,b,c\}\) represent three colors. Then there is a natural correspondence of a word in \(\Sigma^{n}\) to a coloring of the graph, where the \(i\)-th letter in the words corresponds to the color of \(v_{i}\). We construct an automaton with \(3(n-1)+1\)states, as sketched in Figure 1. Notice that this figure only shows the backbone of the construction. Additionally, for each edge \((v_{i},v_{j})\) with \(i<j\) in the graph, we add three types of transitions to the automaton: \(q_{i}\stackrel{{ a}}{{\longrightarrow}}a_{j-i}\), \(q_{i}\stackrel{{ b}}{{\longrightarrow}}b_{j-i}\), \(q_{i}\stackrel{{ c}}{{\longrightarrow}}c_{j-i}\). These three transitions are meant to reflect the three possibilities to improperly color the given graph due to assigning \(v_{i}\) and \(v_{j}\) the same color. Inputs of length \(n\) encode a coloring of the vertices. First notice that the automaton will accept every word of length not equal to \(n\). Namely, words shorter than \(n\) can drive the automaton into one of the states \(q_{1}\) through \(q_{n-1}\).