# Two DFA intersection emptiness connections to SETH & L vs P

(re "fine grained complexity") Wehar has proved that

Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false.

does anyone see any particular key proof difficulty, challenge, implication etc in the inverse of that? ie

if two DFA intersection emptiness is $\Omega(n^2)$ then SETH is true?

this two DFA intersection emptiness problem seems like a key problem to analyze/ resolve because Wehar has also shown that solving the intersection problem for $k$ DFA's in $n^{o(k)}$ time → $NL \subsetneq P$. (are there any other known problems like that? which relate L,P,NP,ExpTime?) the problem also seems similar to an old important problem complete for ExpSpace analyzed by Meyer/ Stockmeyer, "emptiness of regular expressions with squaring."

also, what is known on the best lower space bounds on this problem? (will regard partial answers on these presumably hard questions as ok.)

• "intersection emptiness" ​ = ​ "disjointness" ​ ​ ​ ​ – user6973 Nov 6 '15 at 17:49
• Hi VZN, I'm flattered that you've been posting about the problem that I work on. Some of what you wrote wasn't entirely correct so I submitted edits that are under stackexchange peer review. Thank you. :) – Michael Wehar Nov 6 '15 at 18:48
• – Michael Wehar Nov 6 '15 at 18:50
• hi @Michael am focusing on/ interested in the 2-way special case only/ in particular and (understood) you have looked at n-way case and have more general results. think it is likely the n-way question reduces simply to the 2-way question. dont think anything in the math is technically incorrect. plz feel free to elaborate in Theoretical Computer Science Chat – vzn Nov 6 '15 at 19:13
• @vzn If you can show that solving the 2 DFA problem in $O(n^{2-\epsilon})$ time implies $NL \subsetneq P$, that would be a really nice result. Currently, I can only show that solving the $k$ DFA problem in $n^{o(k)}$ time implies $NL \subsetneq P$. – Michael Wehar Nov 6 '15 at 19:49

SAT is solvable in $O(2^{(1-\epsilon)n})$ time implies the intersection problem is solvable in $O(n^{2-\epsilon})$ time.
To show this, it seems that you would need to provide a reduction from an intersection problem instance of size $n$ to a SAT instance of size $2\cdot log_2(n)$.
• It's possible that there could be a reduction that takes one intersection problem instance of size $n$ to many SAT instances of size $2 \cdot \log_2(n)$. – Michael Wehar Nov 12 '15 at 15:16