On the complexity of intersecting finite state automata and NL versus NP

We consider uniform and non-uniform assumptions for the hardness of an explicit problem from finite state automata theory. First we show that a small improvement in the known straightforward algorithm for this problem can be used to design faster algorithms for subset sum and factoring, and improved deterministic simulations for non-deterministic time.On the other hand, we can use the same improved algorithm for our FSA problem to prove …