1
$\begingroup$

Let $$PATH = \{(G, s, t) | \exists \text{ a directed path from $s$ to $t$ in $G$}\},$$ $$EQ_{DFA} = \{(M_1, M_2) | \text{DFA $M_1$ and $M_2$ over the same alphabet are equivalent}\}.$$ Is there a log space reduction from $PATH$ to $EQ_{DFA}$?

My attempt was to first show that there exists a DFA that accepts a string iff $M_1$ and $M_2$ do. At this point, I am unsure how to reduce the first problem to the second.

$\endgroup$
  • $\begingroup$ Are you sure you need a reduction from $PATH$, or could you also use a reduction from $\overline{PATH}$? Both exist, but the former may be harder. $\endgroup$ – Shaull Mar 20 '18 at 18:52
1
$\begingroup$

It is easier to think about a reduction from $\overline{PATH}$ (since it is NL-complete, this answers your question in the positive). You can treat the graph as a DFA, with initial state $s$ and a single accepting state $t$, and ask whether this automata is equivalent to some DFA for the empty language. Note that the alphabet here is not really important, and you could simply use fresh letters for each vertex.

$\endgroup$
  • $\begingroup$ Could we reduce $PATH$ to $\overline{EQ_{DFA}}$ instead? $\endgroup$ – nicole Mar 20 '18 at 18:58
  • $\begingroup$ A reduction from $L_1$ to $L_2$ is also a reduction from $\overline{L_1}$ to $\overline{L_2}$. $\endgroup$ – Ariel Mar 20 '18 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.