<p>The "inverse" is almost the same as</p>

<blockquote>
  <p>SAT is solvable in $O(2^{(1-\epsilon)n})$ time implies the intersection problem is solvable in
  $O(n^{2-\epsilon})$ time.</p>
</blockquote>

<p>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)$.</p>

<p>This kind of reduction would be very interesting because it would take an instance of one problem to a much smaller instance of another problem.  As a result, this reduction would not be one-to-one.  Actually, there would be exponentially many inputs that map to the same output.</p>

<p>If you know of any interesting reductions of this form, please provide a reference.  Thank you.  :)</p>

CC BY-SA 3.0
2015-11-12T15:16:08.670Z
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
CC BY-SA 3.0
2015-11-06T22:15:30.620Z
2015-11-06T22:15:30.620Z
Michael Wehar
<p>(re <a href="https://cstheory.stackexchange.com/questions/32584/what-are-the-relationships-between-those-hypotheses-in-fine-grained-complexity-t">"fine grained complexity"</a>) Wehar has <a href="https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time">proved</a> that </p>

<blockquote>
  <p>Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow noreferrer">SETH</a> false. </p>
</blockquote>

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

<blockquote>
  <p>if two DFA intersection emptiness is $\Omega(n^2)$ then SETH is true?</p>
</blockquote>

<p>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 <a href="https://en.wikipedia.org/wiki/EXPSPACE" rel="nofollow noreferrer">ExpSpace</a> analyzed by Meyer/ Stockmeyer, "emptiness of regular expressions with squaring."</p>

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

CC BY-SA 3.0
2015-11-06T18:48:45.087Z
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
CC BY-SA 3.0
2015-11-06T18:50:04.293Z
Link: http://cstheory.stackexchange.com/questions/22493/are-there-any-open-problems-left-about-dfas/22563#22563
Michael Wehar
CC BY-SA 3.0
2015-11-06T19:13:45.743Z
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 [chat]
vzn
CC BY-SA 3.0
2015-11-06T19:49:27.363Z
@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
<reference-request><complexity-classes><p-vs-np><exp-time-algorithms><fine-grained>
Two DFA intersection emptiness connections to SETH & L vs P
vzn
# Two DFA intersection emptiness connections to SETH & L vs P

(Asked by: username_0 on 2015-11-06)

(re ["fine grained complexity"](https://cstheory.stackexchange.com/questions/32584/what-are-the-relationships-between-those-hypotheses-in-fine-grained-complexity-t)) Wehar has [proved](https://cstheory.stackexchange.com/questions/29142/deciding-emptiness-of-intersection-of-regular-languages-in-subquadratic-time) that

> Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → [SETH](https://en.wikipedia.org/wiki/Exponential_time_hypothesis) 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](https://en.wikipedia.org/wiki/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.)

**Tags:** reference-request, complexity-classes, p-vs-np, exp-time-algorithms, fine-grained
> **Comments:**
> **username_1**: 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.  :)  
> **username_1**: Link: http://cstheory.stackexchange.com/questions/22493/are-there-any-open-problems-left-about-dfas/22563#22563  
> **username_0**: 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 [chat]  
> **username_1**: @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$.  

---

## 1 answers

### Answer by username_1 on 2015-11-06. Score: 7 | Accepted answer

The "inverse" is almost the same as

> 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)$.

This kind of reduction would be very interesting because it would take an instance of one problem to a much smaller instance of another problem. As a result, this reduction would not be one-to-one. Actually, there would be exponentially many inputs that map to the same output.

If you know of any interesting reductions of this form, please provide a reference. Thank you. :)

> **Comments:**
> **username_1**: 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)$.  

---

