# Problems on Finite Automata and the Exponential Time Hypothesis
## 2 Universality, Equivalence, Intersection: Unary Inputs
This assignment can be represented by the language  
\[L_{j}:=\{a^{2k_{j}}\}\cdot\{a^{p_{i_{j}(1)}\cdots p_{i_{j}(|c_{j}|)}}\}^{*}\]  
with \(0\leqslant z_{k_{j}}<p_{i_{j}(1)}\cdots p_{i_{j}(|c_{j}|)}\) being uniquely determined by \(z_{k_{j}}=\alpha(r)\bmod p_{i_{j}(r)}\) for \(r=1,\ldots,|c(j)|\). As \(p_{i_{j}(1)}\cdots p_{i_{j}(|c_{j}|)}\leqslant p_{n}^{3}\) (3 SAT), \(L_{j}\) can be accepted by a DFA with at most \(p_{n}^{3}\) states. Hence, \(\bigcup_{j=1}^{m}L_{j}\) can be accepted by an NFA with at most \(mp_{n}^{3}\sim mn^{3}(\ln n)^{3}\) many states. In conclusion, there is an NFA \(A\) for \(\bigcup_{j=0}^{m}L_{j}\) with at most \(mp_{n}^{3}\sim mn^{3}(\ln n)^{3}\) many states with \(L(A)\
eq\{a\}^{*}\) iff \(F\) is satisfiable. For the correctness, it is crucial to observe that if \(a^{\ell}\
otin L(A)\) for some \(\ell\geqslant p_{1}\cdots p_{n}\), then also \(a^{\ell\bmod(p_{1}\cdots p_{n})}\
otin L(A)\). Hence, if \(L(A)\
eq\{a\}^{*}\), then \(a^{\ell}\
otin L(A)\) for some \(\ell<p_{1}\cdots p_{n}\). As \(L_{0}\subset L(A)\), \(\ell\) represents an assignment \(\alpha\) that does not falsify each clause (by construction of the sets \(L_{j}\)), so that \(\alpha\) satisfies the given formula. Conversely, if \(\alpha\) satisfies \(F\), then \(\alpha\) can be represented by an integer \(z\), \(0\leqslant z<p_{1}\cdots p_{n}\). Now, \(a^{z}\
otin L_{0}\) as it represents an assignment, but neither \(a^{z}\in L_{j}\) for any \(j>0\), as \(\alpha(c_{j})=1\). Observe that in the more classical setting, this proves that Non-Universality is NP-hard. We like to emphasize a possible method to ETH-based results, namely, analyzing known NP-hardness reductions first and then refining them to get improved ETH-based results. _Unless ETH fails, for any \(\epsilon\in\left(0,\frac{1}{4}\right)\), there is no \(O^{*}\left(2^{o(q^{1/4-\epsilon})}\right)\)-time algorithm for deciding, given a tally NFA \(A\) on \(q\) states, whether \(L(A)=\{a\}^{*}\)._  
Assume that, for any \(\epsilon>0\), there was an \(O^{*}\left(2^{o(q^{1/4-\epsilon})}\right)\)-time algorithm \(\mathcal{A}_{\epsilon}\) for deciding, given a tally NFA \(A\) on \(q\) states, whether \(L(A)=\{a\}^{*}\). Consider some 3 SAT formula with \(n\) variables and \(m\) clauses. We can assume (by the Sparsification Lemma) that this 3 SAT instance is sparse. We already described the construction of [9] above. So, we can obtain in polynomial time an NFA with \(q\approx mn^{3}(\ln n)^{3}\) many states as an instance of Universality. This instance can be solved in time \(O^{*}(2^{o(q^{1/4-\epsilon})})\) by \(\mathcal{A}_{\epsilon}\). Hence, \(\mathcal{A}_{\epsilon}\) can be used to solve the given 3 SAT instance in time  
\[O^{*}\left(2^{o(q^{1/4-\epsilon})}\right)=O^{*}\left(2^{o((m(n\cdot\ln n)^{3}) ^{1/4-\epsilon})}\right)\subseteq O^{*}\left(2^{o(((m+n)\cdot\ln(m+n)^{4})^{1/4 -\epsilon})}\right)\subseteq O^{*}\left(2^{o((n+m)}\right)\,\]  
in the interesting range of \(\epsilon\in\left(0,\frac{1}{4}\right)\), which contradicts ETH. To formally do the necessary computations in the previous theorem (and similar results below), dealing with logarithmic terms in the exponent, we need to understand the correctness of some computations in the \(o(\cdot)\) notation. We exemplify such a computation in the following. Lemma 1: \(\forall\epsilon\in(0,1)\)_: \(o((n\log n)^{\epsilon})\subseteq o(n)\)._Proof. : This statement can be seen by the following line, using the rule of l'Hospital. \[\lim_{n\to\infty}\frac{(n\ln n)^{\epsilon}}{n}=\lim_{n\to\infty}\frac{\epsilon(1 +\ln n)^{\epsilon-1}}{1}=\lim_{n\to\infty}\frac{\epsilon}{(1+\ln n)^{1-\epsilon} }=0\]  
Notice that \(1-\epsilon\in(0,1)\) by our assumption. We are now trying to strengthen the assertion of the previous theorem.