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.

Improve this question
$\endgroup$
1
  • $\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$ Commented Mar 20, 2018 at 18:52

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could we reduce $PATH$ to $\overline{EQ_{DFA}}$ instead? $\endgroup$ Commented Mar 20, 2018 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$ Commented Mar 20, 2018 at 19:00

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.