<p><strong>Simple answer</strong>: If there does exist a more efficient algorithm that runs in $O(n^{\delta})$ time for some $\delta &lt; 2$, then the strong exponential time hypothesis would be refuted.</p>

<hr>

<p>We will prove a stronger theorem and then the simple answer will follow.</p>

<p><strong>Theorem</strong>: If we can solve the intersection non-emptiness problem for two DFA's in $O(n^{\delta})$ time, then any problem that's non-deterministically solvable using only n bits of memory is deterministically solvable in $poly(n)\cdot2^{(\delta n/2)}$ time.</p>

<p><strong>Justification</strong>: Suppose that we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time.  Let a non-deterministic Turing machine M with a read only input tape and a read/write binary work tape be given.  Let an input string x of length n be given.  Suppose that M doesn't access more than n bits of memory on the binary work tape.</p>

<p>A computation of M on input x can be represented by a finite list of configurations.  Each configuration consists of a state, a position on the input tape, a position on the work tape, and up to n bits of memory that represent the work tape.</p>

<p>Now, consider that the work tape was split in half.  In other words, we have a left section of $\frac{n}{2}$ cells and a right section of $\frac{n}{2}$ cells.  Each configuration can be broken up into a left piece and a right piece.  The left piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the left section.  The right piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the right section.</p>

<p>Now, we build a DFA $D_1$ whose states are left pieces and a DFA $D_2$ whose states are right pieces.  The alphabet characters are instructions that say which state to go to, how the tape heads should move, and how the work tape's active cell should be manipulated.</p>

<p>The idea is that $D_1$ and $D_2$ read in a list of instructions corresponding to a computation of M on input x and together verify that it is valid and accepting.  Both $D_1$ and $D_2$ will always agree on where the tape heads are because that information is included in their input characters.  Therefore, we can have $D_1$ verify that the instruction is appropriate when the work tape position is in the left piece and $D_2$ verify when in the right piece.</p>

<p>In total, there are at most $poly(n) \cdot 2^{n/2}$ states for each DFA and at most $poly(n)$ distinct alphabet characters.</p>

<p>By the initial assumption, it follows that we can solve intersection non-emptiness for the two DFA's in $poly(n) \cdot 2^{(\delta n /2)}$ time.</p>

<p>You might find this helpful: <a href="https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/">https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/</a></p>

<hr>

<p>CNF-SAT is solvable using $k+O(\log(n))$ bits of memory where k is the number of variables.  The preceding construction can be used to show that if we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time, then we can solve CNF-SAT in $poly(n) \cdot 2^{(\delta k/2)}$ time.  Therefore, the <strong>simple answer</strong> holds.</p>

<p>Comments, corrections, suggestions, and questions are welcomed.  :)</p>

CC BY-SA 3.0
2015-11-05T05:57:09.283Z
all great but the original question above was for _NFAs;_ does it all still follow? also, some key detail is left out. seems worth a paper. or is it all in your published one? if so plz cite it/ tie in to numbered theorems there etc. also it would be helpful to state this all more in terms of std complexity classes L,P,NP,PSpace,ExpTime etc if possible. also wondering if anything can be said about the direction "strong" 2-way DFA intersection emptiness lower bound ($\Omega(n^2)$?) → SETH...? what needs to be shown for that?
vzn
CC BY-SA 3.0
2015-11-05T16:34:33.277Z
Hi VZN, the intersection problem for NFA's appears slightly harder than the intersection problem for DFA's.  However, this is not the case because there is a parameterized reduction from intersection non-emptiness for $k$ NFA's to intersection non-emptiness for $k$ DFA's.  This is mentioned in my first paper.
Michael Wehar
CC BY-SA 3.0
2015-11-05T16:58:10.610Z
Maybe you can describe in more detail what you mean when you mention 2-way DFA.  The non-emptiness problem for $(2k-2)$-turn two-way DFA's is just as hard as the intersection non-emptiness problem for $k$ one-way DFA's.  Link: http://cs.stackexchange.com/questions/13456/what-is-the-complexity-of-the-emptiness-problem-for-2-way-dfas/48560#48560
Michael Wehar
CC BY-SA 3.0
2015-11-05T17:01:47.490Z
In terms of standard complexity classes, you could state this as something like: $NSpace(2 \cdot \log(n)) \subseteq DTime(n)$ implies SETH is false. When I write $NSpace(2 \cdot \log(n))$, I mean $2\cdot \log(n)$ space for non-deterministic Turing machines with a two-way read only input tape and a two-way read/write binary work tape.
Michael Wehar
CC BY-SA 4.0
2021-03-12T03:51:09.947Z
@MichaelWehar 1. If we can solve intersection of $k$ DFA's in $O(nk)$ time what is the consequence? 2. If we can solve intersection of $k$ DFA's in $O(n^{f(k)})$ time what is the consequence where $f=o(k)$ (might be logarithmic or $\sqrt k$ etc.)?
Turbo
CC BY-SA 4.0
2021-03-12T18:35:45.453Z
@1.. Hi there!  Thank you for your questions.  I assume that you are considering that $k$ can vary with the input.  Regarding (1), this would mean that $PTIME = PSPACE$ because the intersection non-emptiness problem is $PSPACE$-complete (Kozen 1977).  Maybe we could prove additional implications too besides just $PTIME = PSPACE$.  Regarding (2), this would imply that $PTIME \neq NLOGSPACE$ (see my paper from 2014).  This would also imply many additional things so you might want to look at this recent paper too: https://link.springer.com/chapter/10.1007/978-3-030-48516-0_6
Michael Wehar
CC BY-SA 4.0
2021-03-12T18:38:33.700Z
@1.. I actively work on this problem and would always be excited to chat with you about it.  Send me an email anytime.  Thank you and I hope that you have a nice day!  :)
Michael Wehar
CC BY-SA 4.0
2021-03-12T22:02:25.420Z
@MichaelWehar Thank you $\mathsf{PTIME}\neq\mathsf{NL}$ through $n^{o(k)}$ is surprising and counterintuitive to me. 1.) I think I am looking for an assumption consistent to $\mathsf{CH}\neq\mathsf{PSPACE}$ but $\mathsf{CH}=\mathsf{L}$ or possibly $\mathsf{CH}=\mathsf{TC}^0$. For the working hypothesis which is the strongest result on $k$ DFA one can get? 2.) What if $k$ DFA problem is partially fixed parameter tractable which is $f(k)\mathsf{poly}(n)$ algorithm exists where $f(k)$ is superpolynomial or superexponential?
Turbo
CC BY-SA 4.0
2021-03-13T02:50:19.467Z
@MichaelWehar I posted a complete question in https://cstheory.stackexchange.com/questions/48573/dfsa-and-nfsa-intersection-problem.
Turbo
CC BY-SA 4.0
2021-03-13T23:18:46.820Z
@1.. I am still thinking about your question, but for the second part, we still get $PTIME \neq NLOGSPACE$ even if it runs in $f(k) \cdot n^{o(k)}$.  Based on the paper, we can actually prove something even stronger regarding the fixed slices.  Say that $k$-intersection is the $k$th slice, then the result says the following.  If for all $\alpha > 0$, there exists $k$ such that $k$-intersection $\in DTIME(n^{\alpha \cdot k})$, then $PTIME \neq NLOGSPACE$.
Michael Wehar
CC BY-SA 3.0
2015-01-17T03:10:39.173Z
2015-01-20T00:59:07.387Z
2015-01-20T00:59:07.387Z
Michael Wehar
<p>Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input.</p>

<p>Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which computes the product automaton of $M_1,M_2$, but I was wondering if anything more efficient is known.</p>

<blockquote>
  <p>Is there a $o(n^2)$ algorithm for deciding whether $L_1\cap L_2\neq \emptyset$? What is the fastest known algorithm?</p>
</blockquote>

CC BY-SA 3.0
2015-01-14T17:05:46.200Z
If anyone has good ideas please let me know, but currently it's an open problem.  If you could solve this problem in say linear time, then basically any problem solvable by a non-deterministic machine using only n bits of memory could be solved deterministically in $2^{\frac{n}{2}}$ time.
Michael Wehar
CC BY-SA 3.0
2015-01-14T17:10:39.600Z
@MichaelWehar - is linear time algorithm an open question or any sub-quadratic algorithm?
R B
CC BY-SA 3.0
2015-01-14T17:13:54.987Z
I think it's still open for any sub-quadratic.  Some more info: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/
Michael Wehar
CC BY-SA 3.0
2015-01-14T17:16:34.343Z
I work on this problem.  If you're interested, we could chat sometime.  Just send me an email.  :)
Michael Wehar
CC BY-SA 3.0
2015-01-15T05:25:08.450Z
So for example (based on Michael's comment), the strong exponential time hypothesis implies that the exponent should be 2. I think this could also proved to follow from the exponential time hypothesis...
Ryan Williams
CC BY-SA 3.0
2015-01-15T16:51:41.633Z
this is a more recent blog by [rjlipton](https://rjlipton.wordpress.com/2012/11/08/the-power-of-guessing/) citing MWs [newer/ tighter results](http://www.acsu.buffalo.edu/~mwehar/documents/mwehar_INE_5_9_14.pdf) (building on lipton's own). that award-winning paper apparently is the best current known results/ implications & is essentially an answer to the question. essentially a tighter bound proves P≠NL! this also seems to be yet another case of [proving lower bounds by proving upper bounds](http://cstheory.stackexchange.com/questions/3229/proving-lower-bounds-by-proving-upper-bounds)
vzn
CC BY-SA 3.0
2015-01-15T19:18:19.247Z
RB: Assume you can test for emptiness of two DFAs of size $n$ in time $n^{1+\varepsilon}$ with $\varepsilon < 1$. Now, if you have $k$ DFAs of size $n$, you can build the product of the first $k/2$ DFAs and of the remaining $k/2$ DFAs. Then, test for emptiness in time $(n^{k/2})^{1+\varepsilon} = n^{\frac{1}{2}k + \frac{\varepsilon}{2}k}$ which is better than $n^k$.


vzn: This award-winning paper was written by @MichaelWehar who commented in this thread. Michael, perhaps you could submit an answer, if you have time!
Michael Blondin
CC BY-SA 3.0
2015-01-17T00:15:05.707Z
Thanks for the kind comments. Ok, I will write an answer. I'm working on it and should finish a little later tonight.
Michael Wehar
CC BY-SA 3.0
2015-01-17T03:31:28.077Z
@RyanWilliams Hi Ryan, what leads you to think that the weaker exponential time hypothesis implies that we can't solve intersection non-emptiness for two DFA's more quickly?  Someone else suggested this to me once too.  :)
Michael Wehar
<ds.algorithms><automata-theory><regular-language><nondeterminism>
Deciding emptiness of intersection of regular languages in subquadratic time
R B
# Deciding emptiness of intersection of regular languages in subquadratic time

(Asked by: username_0 on 2015-01-14)

Let $L\_1,L\_2$ be two regular languages given by NFAs $M\_1,M\_2$ as input.

Assume we would like to check whether $L\_1\cap L\_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which computes the product automaton of $M\_1,M\_2$, but I was wondering if anything more efficient is known.

> Is there a $o(n^2)$ algorithm for deciding whether $L\_1\cap L\_2\neq \emptyset$? What is the fastest known algorithm?

**Tags:** ds.algorithms, automata-theory, regular-language, nondeterminism

> **Comments:**
> **username_1**: If anyone has good ideas please let me know, but currently it's an open problem.  If you could solve this problem in say linear time, then basically any problem solvable by a non-deterministic machine using only n bits of memory could be solved deterministically in $2^{\frac{n}{2}}$ time.  
> **username_0**: @MichaelWehar - is linear time algorithm an open question or any sub-quadratic algorithm?  
> **username_1**: I think it's still open for any sub-quadratic.  Some more info: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/  
> **username_1**: I work on this problem.  If you're interested, we could chat sometime.  Just send me an email.  :)  
> **username_2**: So for example (based on Michael's comment), the strong exponential time hypothesis implies that the exponent should be 2. I think this could also proved to follow from the exponential time hypothesis...  
> **username_3**: this is a more recent blog by [rjlipton](https://rjlipton.wordpress.com/2012/11/08/the-power-of-guessing/) citing MWs [newer/ tighter results](http://www.acsu.buffalo.edu/~mwehar/documents/mwehar_INE_5_9_14.pdf) (building on lipton's own). that award-winning paper apparently is the best current known results/ implications & is essentially an answer to the question. essentially a tighter bound proves P≠NL! this also seems to be yet another case of [proving lower bounds by proving upper bounds](http://cstheory.stackexchange.com/questions/3229/proving-lower-bounds-by-proving-upper-bounds)  
> **username_4**: RB: Assume you can test for emptiness of two DFAs of size $n$ in time $n^{1+\varepsilon}$ with $\varepsilon < 1$. Now, if you have $k$ DFAs of size $n$, you can build the product of the first $k/2$ DFAs and of the remaining $k/2$ DFAs. Then, test for emptiness in time $(n^{k/2})^{1+\varepsilon} = n^{\frac{1}{2}k + \frac{\varepsilon}{2}k}$ which is better than $n^k$.   username_3: This award-winning paper was written by @MichaelWehar who commented in this thread. Michael, perhaps you could submit an answer, if you have time!  
> **username_1**: Thanks for the kind comments. Ok, I will write an answer. I'm working on it and should finish a little later tonight.  
> **username_1**: @RyanWilliams Hi Ryan, what leads you to think that the weaker exponential time hypothesis implies that we can't solve intersection non-emptiness for two DFA's more quickly?  Someone else suggested this to me once too.  :)  

---

## 1 answers

### Answer by username_1 on 2015-01-17. Score: 26 | Accepted answer

**Simple answer**: If there does exist a more efficient algorithm that runs in $O(n^{\delta})$ time for some $\delta < 2$, then the strong exponential time hypothesis would be refuted.

---

We will prove a stronger theorem and then the simple answer will follow.

**Theorem**: If we can solve the intersection non-emptiness problem for two DFA's in $O(n^{\delta})$ time, then any problem that's non-deterministically solvable using only n bits of memory is deterministically solvable in $poly(n)\cdot2^{(\delta n/2)}$ time.

**Justification**: Suppose that we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time. Let a non-deterministic Turing machine M with a read only input tape and a read/write binary work tape be given. Let an input string x of length n be given. Suppose that M doesn't access more than n bits of memory on the binary work tape.

A computation of M on input x can be represented by a finite list of configurations. Each configuration consists of a state, a position on the input tape, a position on the work tape, and up to n bits of memory that represent the work tape.

Now, consider that the work tape was split in half. In other words, we have a left section of $\frac{n}{2}$ cells and a right section of $\frac{n}{2}$ cells. Each configuration can be broken up into a left piece and a right piece. The left piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the left section. The right piece consists of the state, the position on the input tape, the position on the work tape, and the $\frac{n}{2}$ bits from the right section.

Now, we build a DFA $D\_1$ whose states are left pieces and a DFA $D\_2$ whose states are right pieces. The alphabet characters are instructions that say which state to go to, how the tape heads should move, and how the work tape's active cell should be manipulated.

The idea is that $D\_1$ and $D\_2$ read in a list of instructions corresponding to a computation of M on input x and together verify that it is valid and accepting. Both $D\_1$ and $D\_2$ will always agree on where the tape heads are because that information is included in their input characters. Therefore, we can have $D\_1$ verify that the instruction is appropriate when the work tape position is in the left piece and $D\_2$ verify when in the right piece.

In total, there are at most $poly(n) \cdot 2^{n/2}$ states for each DFA and at most $poly(n)$ distinct alphabet characters.

By the initial assumption, it follows that we can solve intersection non-emptiness for the two DFA's in $poly(n) \cdot 2^{(\delta n /2)}$ time.

You might find this helpful: <https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/>

---

CNF-SAT is solvable using $k+O(\log(n))$ bits of memory where k is the number of variables. The preceding construction can be used to show that if we can solve intersection non-emptiness for two DFA's in $O(n^{\delta})$ time, then we can solve CNF-SAT in $poly(n) \cdot 2^{(\delta k/2)}$ time. Therefore, the **simple answer** holds.

Comments, corrections, suggestions, and questions are welcomed. :)

> **Comments:**
> **username_3**: all great but the original question above was for _NFAs;_ does it all still follow? also, some key detail is left out. seems worth a paper. or is it all in your published one? if so plz cite it/ tie in to numbered theorems there etc. also it would be helpful to state this all more in terms of std complexity classes L,P,NP,PSpace,ExpTime etc if possible. also wondering if anything can be said about the direction "strong" 2-way DFA intersection emptiness lower bound ($\Omega(n^2)$?) → SETH...? what needs to be shown for that?  
> **username_1**: Hi VZN, the intersection problem for NFA's appears slightly harder than the intersection problem for DFA's.  However, this is not the case because there is a parameterized reduction from intersection non-emptiness for $k$ NFA's to intersection non-emptiness for $k$ DFA's.  This is mentioned in my first paper.  
> **username_1**: Maybe you can describe in more detail what you mean when you mention 2-way DFA.  The non-emptiness problem for $(2k-2)$-turn two-way DFA's is just as hard as the intersection non-emptiness problem for $k$ one-way DFA's.  Link: http://cs.stackexchange.com/questions/13456/what-is-the-complexity-of-the-emptiness-problem-for-2-way-dfas/48560#48560  
> **username_1**: In terms of standard complexity classes, you could state this as something like: $NSpace(2 \cdot \log(n)) \subseteq DTime(n)$ implies SETH is false. When I write $NSpace(2 \cdot \log(n))$, I mean $2\cdot \log(n)$ space for non-deterministic Turing machines with a two-way read only input tape and a two-way read/write binary work tape.  
> **username_5**: @MichaelWehar 1. If we can solve intersection of $k$ DFA's in $O(nk)$ time what is the consequence? 2. If we can solve intersection of $k$ DFA's in $O(n^{f(k)})$ time what is the consequence where $f=o(k)$ (might be logarithmic or $\sqrt k$ etc.)?  
> **username_1**: @1.. Hi there!  Thank you for your questions.  I assume that you are considering that $k$ can vary with the input.  Regarding (1), this would mean that $PTIME = PSPACE$ because the intersection non-emptiness problem is $PSPACE$-complete (Kozen 1977).  Maybe we could prove additional implications too besides just $PTIME = PSPACE$.  Regarding (2), this would imply that $PTIME \neq NLOGSPACE$ (see my paper from 2014).  This would also imply many additional things so you might want to look at this recent paper too: https://link.springer.com/chapter/10.1007/978-3-030-48516-0_6  
> **username_1**: @1.. I actively work on this problem and would always be excited to chat with you about it.  Send me an email anytime.  Thank you and I hope that you have a nice day!  :)  
> **username_5**: @MichaelWehar Thank you $\mathsf{PTIME}\neq\mathsf{NL}$ through $n^{o(k)}$ is surprising and counterintuitive to me. 1.) I think I am looking for an assumption consistent to $\mathsf{CH}\neq\mathsf{PSPACE}$ but $\mathsf{CH}=\mathsf{L}$ or possibly $\mathsf{CH}=\mathsf{TC}^0$. For the working hypothesis which is the strongest result on $k$ DFA one can get? 2.) What if $k$ DFA problem is partially fixed parameter tractable which is $f(k)\mathsf{poly}(n)$ algorithm exists where $f(k)$ is superpolynomial or superexponential?  
> **username_5**: @MichaelWehar I posted a complete question in https://cstheory.stackexchange.com/questions/48573/dfsa-and-nfsa-intersection-problem.  
> **username_1**: @1.. I am still thinking about your question, but for the second part, we still get $PTIME \neq NLOGSPACE$ even if it runs in $f(k) \cdot n^{o(k)}$.  Based on the paper, we can actually prove something even stronger regarding the fixed slices.  Say that $k$-intersection is the $k$th slice, then the result says the following.  If for all $\alpha > 0$, there exists $k$ such that $k$-intersection $\in DTIME(n^{\alpha \cdot k})$, then $PTIME \neq NLOGSPACE$.  

---

