# Problems on Finite Automata and the Exponential Time Hypothesis
## 2 Universality, Equivalence, Intersection: Unary Inputs  
The simplest interesting question on tally finite automata is the following one. Given an NFA \(A\) with input alphabet \(\{a\}\), is \(L(A)=\{a\}\)*? In [9], the corresponding problem for regular expressions was examined and shown to be CoNP-complete. This problem is also known as NEC (Non-empty Complement). As the reduction given in [9] starts off from 3 SAT, we can easily analyze the proof to obtain the following result. In fact, it is often a good strategy to first start off with known NP-hardness results to see how these can be interpreted in terms of ETH-based lower bounds. However, as we can also see with this example, this recipe does not always yield results that match known upper bounds. However, the analysis often points to weak spots of the hardness construction, and the natural idea is to attack these weak spots afterwards. This is exactly the strategy that we will follow in this first problem that we consider in this paper. We are sketching the construction for NP-hardness (as a reduction from 3 SAT as in the paper of [PERSON] and [PERSON]) in the following for tally NFAs. Let \(F\) be a given CNF formula with variables \(x_{1},\ldots,x_{n}\). \(F\) consists of the clauses \(c_{1},\ldots,c_{m}\). After a little bit of cleanup, we can assume that each variable occurs at most once in each clause. Let \(p_{1},\ldots,p_{n}\) be the first \(n\) prime numbers. It is known that \(p_{n}\leqslant(n\ln(n\ln n)))\). To simplify the \begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{**\# of States**} & \multirow{2}{*}{\(\Sigma\)} & \multicolumn{2}{c}{**Intersection**} \\ \cline{3-4}  & & **Lower Bound** & **Upper Bound** \\ \hline
2 & & & O(1), i.e., in P \\
3 & unary & & O(1), i.e., in P \\
3 & binary & & O(1), i.e., in P \\
3 & unbounded & \(o(k)\) & \(k\) & Proposition 2 \\ \(q\) & unary & \(o(\min(k\sqrt{\log q},\sqrt{q}))\) & \(\min(k\log q,1.5\cdot q)\) & Theorem 3 \& Proposition 1 \\ \(q\) & binary & \(o(\min(k,2^{q}))\) & \(\min(k\log q,2^{q}\log q)\) & Proposition 3 \& Proposition 4 \\ \(q\) & unbounded & \(o(k\log q)\) & \(k\log q\) & Proposition 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Intersection; functions refer to exponents of bounding functions. \begin{table}
\begin{tabular}{l l l} \hline \hline
**NFA** & **Unary Inputs** & **Binary Inputs** \\ \hline Non-Universality & NP-complete & PSPACE-complete \\ Inequivalence & NP-complete & PSPACE-complete \\ Intersection Non-emptiness & NP-complete & PSPACE-complete \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The classical complexity status of three types of problems on nondeterministic finite automata. following argument, we will only use that \(p_{n}\sim n\ln n\), as shown in ([10], Satz, p. 214). If a natural number \(z\) satisfies  
\[\forall i:1\leqslant i\leqslant n\implies(z=0\bmod p_{i}\lor z=1\bmod p_{i})\,\]  
then \(z\) represents an assignment \(\alpha\) to \(x_{1},\ldots,x_{n}\) with \(\alpha(x_{i})=z\bmod p_{i}\). Then, we say that \(z\) satisfies \(F\) if this assignment satisfies \(F\). Clearly, if \(z\in\{a^{j}\}\{a^{p_{k}}\}^{*}\) for some \(2\leqslant j<p_{k}\), then \(z\) cannot represent any assignment, as \(z\bmod p_{k}\) is neither \(0\) nor \(1\). (This case does not occur for \(p_{1}=2\).) There is a DFA for \(\{a^{j}\}\{a^{p_{k}}\}^{*}\) with \(p_{k}+1\leqslant p_{n}\) states. Moreover, there is even an NFA \(A_{0}\) for  
\[L_{0}:=\bigcup_{k=2}^{n}\bigcup_{j=2}^{p_{k}-1}\{a^{j}\}\{a^{p_{k}}\}^{*}\]  
with at most \(np_{n}\sim n^{2}\ln n\) many states. To each clause \(c_{j}\) with variables \(x_{i_{j}(1)},\ldots,x_{i_{j}(|c_{j}|)}\) occurring in \(c_{j}\), for a suitable injective index function \(i_{j}:\{1,\ldots,|c_{j}|\}\to\{1,\ldots,n\}\), there is a unique assignment \(\alpha\in\{0,1\}^{|c_{j}|}\) to these variables that falsifies \(c_{j}\).