# Problems on Finite Automata and the Exponential Time Hypothesis
## 2 Universality, Equivalence, Intersection: Unary Inputs
To formally describe invalid colorings, we also need a function \(\mathbf{blk}\) that associates the block number to a given vertex index (where the coloring information can be found), and partial functions \(\mathbf{col}_{j}:\{0,\ldots,p_{\mathbf{blk}(j)}-1\}\rightarrow\{0,1,2\}\) for each vertex index \(j\), yielding the coloring of vertex \(v_{j}\). We can cyclically extend \(\mathbf{col}_{j}\) by setting \(\mathbf{col}_{j}(n):=\mathbf{col}_{j}(n\text{ mod }p_{\mathbf{blk}(j)})\) whenever \(\mathbf{col}_{j}\) is defined. For each edge \(e_{j}\) with end vertices \(v_{a(j)},v_{\omega(j)}\) with \(1\leq a(j)<\omega(j)\leq n\) there are three colorings of \(\{v_{a(j)},v_{\omega(j)}\}\) that violate the properness condition. We can capture such a violation in the language \(L_{j}:=\{a^{2}:\mathbf{col}_{a(j)}(z)=\mathbf{col}_{\omega(j)}(z)\}\). \(L_{j}\) is regular, as  
\[L_{j}=M_{j}\cdot\{a^{p_{\mathbf{blk}(a(j))}\cdot p_{\mathbf{blk}(\omega(j))} \}^{*}\,,\]  
with  
\[M_{j}:=\{a^{2}:0\leq z<p_{\mathbf{blk}(a(j))}\cdot p_{\mathbf{blk}(\omega(j)) }\wedge\mathbf{col}_{a(j)}(z)=\mathbf{col}_{\omega(j)}(z)\}\]  
being finite, as \(p_{\mathbf{blk}(a(j))}p_{\mathbf{blk}(\omega(j))}\leq 16n^{2}\). So, \(L_{j}\) can be accepted by a DFA with at most \(n^{2}\) states, ignoring constant factors. Hence, \(\bigcup_{j=1}^{m}L_{j}\) can be accepted by an NFA with at most \(mn^{2}\) many states. In conclusion, there is an NFA \(A\) for \(\bigcup_{j=0}^{m}L_{j}\) with at most \(mn^{2}\) many states with \(L(A)\
eq\{a\}^{*}\) iff \(G\) is 3-colorable. For the correctness, it is crucial to observe that if \(a^{r}\
otin L(A)\) for some \(r\geq p_{1}\cdots p_{l}\), then also \(a^{r\text{ mod }(p_{1}\cdots p_{l})}\
otin L(A)\). Hence, if \(L(A)\
eq\{a\}^{*}\), then \(a^{r}\
otin L(A)\) for some \(r<p_{1}\cdots p_{l}\). As \(L_{0}\subset L(A)\), \(r\) represents a coloring \(c\) that does not color any edge improperly (by construction of the sets \(L_{j}\)). Conversely, if \(c\) properly colors \(G\), then \(c\) can be represented by an integer \(z\), \(0\leq z<p_{1}\cdots p_{l}\). Now, \(a^{z}\
otin L_{0}\) as it represents a coloring, but neither \(a^{z}\in L_{j}\) for any \(j>0\), as \(c(v_{a(j)})\
eq c(v_{\omega(j)})\). Observe that in the more classical setting, this proves that Universality is CoNP-hard. As ETH rules out O* \(\left(2^{o(n+m)}\right)\)-algorithms for solving 3-Coloring on \(m\)-edge graphs with \(n\) vertices, we can assume that we have \((m+n)^{3}\) as an upper bound on the number \(q\) of states of the NFA instance constructed as described above. If there would be an \(O^{*}\left(2^{o(q^{1/3})}\right)\)-time algorithm for Universality of \(q\)-state tally NFAs, then we would find an algorithm for solving 3-Coloring that runs in time \(O^{*}\left(2^{o(((n+m)^{3})^{1/3})}\right)\). This would contradict ETH. How good is this improved bound? There is a pretty easy algorithm to solve the universality problem. First, transform the given tally NFA into an equivalent tally DFA, then turn it into a DFA accepting the complement and check if this is empty. The last two steps are clearly doable in linear time, measured in the size of the DFA obtained in the first step. For the conversion of a \(q\)-state tally NFA into an equivalent \(q^{\prime}\)-state DFA, it is known that \(q^{\prime}=2^{\Theta(\sqrt{q^{l}\log q})}\) is possible but also necessary [11]. The precise estimate on \(q^{\prime}\) is  
\[\forall i:1\leqslant i\leqslant n\implies(z=0\bmod p_{i}\lor z=1\bmod p_{i})\,\]0  
also known as [PERSON]'s function. It is tightly related to the prime number estimate for \(p_{n}\) we have already seen. So, in a sense, the ETH bound poses the question if there are other algorithms to decide universality for tally NFAs, radically different from the proposed one, not using DFA conversion first.