# PSPACE-completeness of DFA intersection problem

Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness.

It seems to me that I understand, why this problem lies in PSPACE: if $$n_1,\dots, n_k$$ are the numbers of states, then one can take the product of these DFA and get that if there is a recognisable string, then there is a recognisable string of length $$\le n_1\dots n_k$$. Then we can non-deterministically guess this string and use Savitch theorem.

So, the question is, how to prove PSPACE-hardness? Should I reduce any given TM to this problem, or maybe some known problem like QBF?

Your proof that the problem is in PSPACE is not quite correct. The problem is that the product $$n_1 \cdots n_k$$ is not bounded by a polynomial in the input length $$n_1 + \dots + n_k$$. The correct way to do it is to directly apply Savitch's theorem to the NPSPACE machine that nondeterministically guesses a path through the product graph. The difference is that, while an accepting path can indeed be as long as $$n_1 \dots n_k$$, the machine only guesses one symbol at a time and never stores the entire input string in memory, so we stay within the polynomial space limit.