Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.00297 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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}$.