Several common non-emptiness problems have been shown to be complete for complexity classes ranging from Deterministic Logspace up to PSPACE.
Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a non-empty intersection.
There is a common exponential time algorithm that solves the intersection non-emptiness problem based on the Cartesian product construction introduced by Michael O. Rabin and Dana Scott.
Whether or not such a path exists is equivalent to determining if any string is accepted by all of the automata in the list.
The intersection non-emptiness problem was shown to be PSPACE-complete in a work by Dexter Kozen in 1977.