On the complexity of intersecting finite state automata and NL versus NP
✍ Scribed by George Karakostas; Richard J. Lipton; Anastasios Viglas
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 256 KB
- Volume
- 302
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
We consider uniform and non-uniform assumptions for the hardness of an explicit problem from ÿnite 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 complexity class separation results (NL is not equal to P, or NP for the non-uniform case).
This result can be viewed either as a hardness result for the FSA intersection problem, or as a method for separating NL from P or NP. It is interesting to note that this approach is based on a more general method for separating two complexity classes, using algorithms rather than lower bounds.