# How to show that FPATH is in NL?

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?

• Try to show that this problem is in co-NL and then use Immerman-Szelepcsényi to put in in NL. – Louis May 20 '14 at 21:53
• But if i non-deterministically select a path from a1 to an, how do I keep track of that I have been through the sequence in a correct order without using too much space? And thanks for the tip, I hadn't thought about that approach :) – user2795095 May 20 '14 at 22:09
• "I know that PATH is NL-complete" -- no, you can't; showing that it's in NL is part of showing that it's NL-complete. Why do you talk about space but use NTIME(log n)? Does that not mean that you can use only logarithmic time, too? – Raphael May 21 '14 at 6:35
• Well, it's a fact that PATH is NL-complete, and I have the proof for this. Since PATH is similar to FPATH, i figure this is useful somehow. And I meant to write SPACE(log n), it's edited now. – user2795095 May 21 '14 at 7:46
• For the modified problem, try to think about gluing together some copies of a graph to reduce it to a single instance of PATH in log space. – Louis May 22 '14 at 18:46

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.