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?

  • $\begingroup$ Try to show that this problem is in co-NL and then use Immerman-Szelepcsényi to put in in NL. $\endgroup$
    – Louis
    Commented May 20, 2014 at 21:53
  • $\begingroup$ 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 :) $\endgroup$ Commented May 20, 2014 at 22:09
  • $\begingroup$ "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? $\endgroup$
    – Raphael
    Commented May 21, 2014 at 6:35
  • $\begingroup$ 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. $\endgroup$ Commented May 21, 2014 at 7:46
  • $\begingroup$ 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. $\endgroup$
    – Louis
    Commented May 22, 2014 at 18:46

1 Answer 1


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.

  • $\begingroup$ Thank you so much, but there is a fact that I forgot to add to the language. It is allowed that the path goes through other nodes in G, but it has to visit node a1 before a2 and so on (edited the question also). Do you have a good solution for this? I'm not to good at the L and NL class. $\endgroup$ Commented May 21, 2014 at 7:48
  • $\begingroup$ @user2795095 Louis has solved one question for you. Solve the rest on your own. $\endgroup$ Commented May 21, 2014 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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