# Problems on Finite Automata and the Exponential Time Hypothesis
## 5 SETH-Based Bounds: Length-Bounded Problem Variants  
[PERSON] and [PERSON] studied in [32] the complexity of a so-called bounded version of Universality, where in addition to the automaton \(A\) with input alphabet \(\Sigma\), a number \(k\) (encoded in unary) is input, and the question is if \(\Sigma^{\leq k}\subseteq L(A)\). This problem is again CoNP-complete for general alphabets. The proof given in [32] is by reduction from the \(n\)-Step Halting Problem for NTMs, somehow modifying earlier constructions of [33]. Our reduction from 3-Coloring given above also shows the mentioned CoNP-completeness result in a more standard way. Our ETH-based result also transfers into this setting; possibly, there are now better algorithms for solving Bounded Universality, as this problem might be a bit easier compared to Universality. We will discuss this a bit further below. Notice that in [29], another SETH-based result relating to synchronizing words was derived. Namely, it was shown that (under SETH) there is no algorithm that determines, given a deterministic finite semi-automaton \(A=(Q,\Sigma,\{\mu_{a}\mid a\in\Sigma\})\) and an integer \(\ell\), whether or not there is a synchronizing word for \(A\), and that runs in time \(O^{*}\left((|\Sigma|-\epsilon)^{\ell}\right)\) for any \(\epsilon>0\). Here, \(\Sigma\) is part of the input; the statement is also true for fixed binary input alphabets. We will use this result now to show some lower bounds for the bounded versions of more classical problems we considered above. Theorem 5.1: _There is an algorithm with running time \(O^{*}\left(|\Sigma|^{\ell}\right)\) that, given \(k\) DFAs over the input alphabet \(\Sigma\) and an integer \(\ell\), decides whether or not there is a word \(w\in\Sigma^{\leq\ell}\) accepted by all these DFAs. Conversely, there is no algorithm that solves this problem in time \(O^{*}\left((|\Sigma|-\epsilon)^{\ell}\right)\) for any \(\epsilon>0\), unless SETH fails._  
**Proof. ** The mentioned algorithm simply tests all words of length up to \(\ell\). We show how to find a synchronizing word of length at most \(\ell\) for a given DFSA \(A=(Q,\Sigma,\{\mu_{a}\mid a\in\Sigma\})\) and an integer \(\ell\) that runs in time \(O((|\Sigma|-\varepsilon)^{\ell})\), assuming for the sake of contradiction that there is an algorithm with such a running time for Bounded DFA-Intersection. From \(A\), we build \(|Q|^{2}\) many DFAs \(A_{s,f}\) (namely, with start state \(s\) and with unique final state \(f\), while the transition function of all \(A_{s,f}\) is identical, corresponding to \(\{\mu_{a}\mid a\in\Sigma\}\)). Furthermore, let \(A^{\ell}\) be the automaton that accepts any word of length at most \(\ell\). Now, we create \(|Q|\) many instances of \(I_{f}\) of Bounded DFA-Intersection. Namely, \(I_{f}\) is given by \(\{A_{s,f}\mid s\in Q\}\cup\{A^{\ell}\}\). Now, \(A\) has a synchronizing word of length at most \(\ell\) if and only if for some \(f\in Q\), \(I_{f}\) is a YES-instance. Clearly, the above reasoning implies that there is no \(O^{*}\left((|\Sigma|-\varepsilon)^{\ell}\right)\)-time algorithm for Bounded NFA-Intersection, unless SETH fails. More interestingly, we can use state complementation and a variant of the NFA union construction to show the following result. **Corollary 4**: _There is an algorithm with running time \(O^{*}\left(|\Sigma|^{\ell}\right)\) that, given some NFA over the input alphabet \(\Sigma\) and an integer \(\ell\), decides whether or not there is a word \(w\in\Sigma^{\leq\ell}\) not accepted by this NFA. Conversely, there is no algorithm that solves this problem in time \(O^{*}\left((|\Sigma|-\varepsilon)^{\ell}\right)\) for any \(\varepsilon>0\), unless SETH fails._  
Clearly, this implies a similar result for Bounded NFA-Equivalence.