Unconditional Time and Space Complexity Lower Bounds for Intersection Non-Emptiness
It addresses computational complexity theory problems for researchers in theoretical computer science, with incremental advancements building on prior work.
The paper strengthens conditional time complexity lower bounds for the Intersection Non-Emptiness Problem for Deterministic Finite Automata (DFA's) and uses a recent breakthrough to derive an unconditional lower bound of Ω(n²/(log³(n) loglog²(n))).
We reinvestigate known lower bounds for the Intersection Non-Emptiness Problem for Deterministic Finite Automata (DFA's). We first strengthen conditional time complexity lower bounds from T. Kasai and S. Iwata (1985) which showed that Intersection Non-Emptiness is not solvable more efficiently unless there exist more efficient algorithms for non-deterministic logarithmic space ($\texttt{NL}$). Next, we apply a recent breakthrough from R. Williams (2025) on the space efficient simulation of deterministic time to show an unconditional $Ω(\frac{n^2}{\log^3(n) \log\log^2(n)})$ time complexity lower bound for Intersection Non-Emptiness. Finally, we consider implications that would follow if Intersection Non-Emptiness for a fixed number of DFA's is computationally hard for a fixed polynomial time complexity class. These implications include $\texttt{PTIME} \subseteq \texttt{DSPACE}(n^c)$ for some $c \in \mathbb{N}$ and $\texttt{PSPACE} = \texttt{EXPTIME}$.