1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Try to show that this problem is in co-NL and then use Immerman-Szelepcsényi to put in in NL. $\endgroup$ – Louis May 20 '14 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$ – user2795095 May 20 '14 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 May 21 '14 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$ – user2795095 May 21 '14 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 May 22 '14 at 18:46
0
$\begingroup$

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.

$\endgroup$
  • $\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$ – user2795095 May 21 '14 at 7:48
  • $\begingroup$ @user2795095 Louis has solved one question for you. Solve the rest on your own. $\endgroup$ – Yuval Filmus May 21 '14 at 18:04

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.