If you want to make money online : Register now

[Solved]: How to show that FPATH is in NL?

, , No Comments
Problem Detail: 

Consider this problem:

$\qquad\displaystyle \mathsf{FPATH} = \{\langle G, a_1,\dots,a_n\rangle \mid G \text{ is a digraph with directed path } (a_1,\dots,a_n)\}$

It's allowed to visit nodes outside the sequence, but a1 must be visited before a2 and so on.

I am having big trouble trying to show that this language is NL-complete. I have tried finding an algorithm for a TM that decides this problem in NSPACE(log n), but I can't seem to find a good solution. I know that PATH is NL-complete, so I guess I can use that fact. My problem is finding an algorithm that somehow has to know that is has been through the sequence $a_1$ to $a_n$, but how can I do this when the worktape only can use $\log n$ space?

Asked By : user2795095

Answered By : Louis

Turning my comment into an answer for the question in the title, the Immerman-Szelepcsényi Theorem says that NL = coNL. This means it's enough to show that FPATH is in coNL. For that, observe that the path $a_1,a_2,\ldots, a_n$ is not in $G$ if and only if some edge $a_ia_{i+1}$ is not present. Since you just need to guess $i$, that's all you need to write down.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25936

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback