# space complexity of DFA intersection problem

the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper significance in computational complexity theory. it is O(n2) time with no better lower bounds known, and tight bounds possibly having major implications on multiple complexity class separations. looking for insight/ refs.

what is the best known space complexity of determining DFA intersection (emptiness)? how does the best known algorithm work?

Solving intersection Non-Emptiness for 2 DFA's:

It essentially just becomes a reachability problem for the product DFA.

• Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ space.

• Or, we can solve it non-deterministically with $O(\log(n))$ space.

• By Savitch's Theorem, we can also solve it deterministically in $2^{O(\log^2(n))}$ time using $O(\log^2(n))$ space.

To the best of my knowledge, it is not known if we can solve it deterministically in polynomial time using $O(n^{2-\epsilon})$ space.

Feel free to share any thoughts or ideas in the comments. :)