# 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?

• There is a difference between computing the product DFA and determining if the intersection is empty. For computing the product DFA, take a look at: cstheory.stackexchange.com/questions/152/… Nov 8, 2015 at 19:40

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. :)