# Problems on Finite Automata and the Exponential Time Hypothesis
## 2 Universality, Equivalence, Intersection: Unary Inputs
There are actually two weak spots in the mentioned reduction: (a) The \(\epsilon\)-term in the statement of the theorem is due to logarithmic factors introduced by encodings with prime numbers; however, the encodings suggested in [9] leave rather big gaps of numbers that are not coding any useful information. (b) The \(\frac{4}{7}\)-term is due to writing down all possible reasons for not satisfying any clause, which needs about \(\tilde{O}(mn^{3})\) many states (ignoring logarithmic terms) on its own; so, we are looking for a problem that allows for cheaper encodings of conflicts. To achieve our goals, we need the following theorem, see [5], Theorem 14.6. **Theorem 1**. : _Unless ETH fails, there is no \(O^{*}\left(2^{o(m+n)}\right)\)-time algorithm for deciding if a given \(m\)-edge \(n\)-vertex graph has a (proper) 3-coloring._  
As it seems to be hard to find proof details anywhere in the literature, we provide them in the following. Proof. : Namely, in some standard NP-hardness reduction (from 3 SAT via 3-Not-All-Equal-SAT), we could first sparsify the given 3 SAT instance, obtaining an instance with \(N\) variables and \(M\) clauses. Also, we can assume that \(N\in O(M)\). The 3-NAE-SAT instance would replace each clause \(c=\ell_{1}\vee\ell_{2}\vee\ell_{3}\) of the 3 SAT instance by \(c^{\prime}=\ell_{1}\vee\ell_{2}\lor x_{\epsilon}\) and \(c^{\prime}=\ell_{3}\vee\
eg x_{\epsilon}\), where \(x_{\epsilon}\) is a special new variable. Hence, this instance has \(N^{\prime}=N+M\) variables and \(M^{\prime}=2M\) clauses. The 3-coloring instance \(G=(V,E)\) that we then obtain has \(2N^{\prime}+3\) vertices and \(3N^{\prime}+3\) edges in the variable gadgets, as well as \(6M^{\prime}\) vertices and \(9M^{\prime}\) edges in the clause gadgets, plus \(3M^{\prime}\) edges to connect the clause with the variable gadgets. Hence, in particular \(|E|\in O(M)\). This rules out \(O^{*}\left(2^{o(m)}\right)\)-time algorithms for solving 3-Coloring on \(m\)-edge graphs. The previous result can be used, together with the sketched ideas, to prove the following theorem. **Theorem 2**. : _Unless ETH fails, there is no \(O^{*}\left(2^{o(4^{1/3})}\right)\)-time algorithm for deciding, given a tally NFA \(A\) on \(q\) states, whether \(L(A)=\{a\}^{*}\)._  
Proof. : We are now explaining a reduction from 3-Coloring to tally NFA Universality. Let \(G=(V,E)\) be a given graph with vertices \(v_{1},\ldots,v_{n}\). \(E\) consists of the edges \(e_{1},\ldots,e_{m}\). Let \(P=\{p\mid p\text{ is a prime and }2n\leq p<4n\}\). To simplify the following argument, we will only use that the expected number of primes below \(n\) is at least \(n/\ln n\), as shown in [10], Satz, p. 214. Hence we can assume \(P\) contains at least \(n/\log n\) primes \(p_{1},\ldots,p_{l}\) for \(l=\lceil n/\log n\rceil\). (For the sake of clarity of presentation, we ignore some small multiplicative constants here and in the following.) We group the vertices of \(V\) into blocks of size \(\log n\). A coloring within such a block can be encoded by a number between \(0\) and \(3^{\log n}\leq 2n\). Hence, a coloring is described by an \(l\)-tuple \(z_{1},\ldots,z_{l}\) of numbers. If a natural number \(z\) satisfies  
\[\forall i:1\leq i\leq n/\log n\implies z\equiv z_{i}\bmod p_{i},\]  
where \(z_{i}\) is representing the encoding of a block, then \(z\) is an encoding of a coloring of some vertex from \(V\). There is a DFA for \(\{a^{j}\}\{a^{p_{k}}\}^{*}\) with at most \(4n\) states, where \(j\) is number that does not represent a valid coloring of the \(k\)-th block. Similarly, there is also a DFA for \(\bigcup_{j\text{ is not valid}}\{a^{j}\}\{a^{p_{k}}\}^{*}\) with this number of states (only the set of final states changes). Moreover, there is even an NFA \(A_{0}\) for  
\[L_{0}:=\bigcup_{k=1}^{l}\bigcup_{j\text{ is not valid}}\{a^{j}\}\{a^{p_{k}}\}^{*}\]  
with at most \(lp_{n+1}\sim n^{2}\) states.