3
$\begingroup$

From the book The Nature of Computation by Moore and Mertens, exercise 8.9:

Consider the problem ACYCLIC GRAPH of telling whether a directed graph is acyclic. Show that the problem is in NL, and then show that the problem is NL-complete.

I am mainly interested in the first part. It's quite easy to show that it's in coNL (just guess a walk, vertex by vertex, from a vertex $v$ that returns to $v$), and then we can use the Immerman-Szelepcsényi Theorem to prove that it's in NL.
But I was not able to construct a Turing machine directly, i.e. a machine that shows that the problem is in NL without the help of Immerman-Szelepcsényi or the construction from their proof. My question thus is:

How can I show directly that ACYCLIC GRAPH is in NL?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Actually, you can't guess a cycle in NL because a cycle can have a linear number of vertices so can't be guaranteed to be stored in logarithmic space. You need to guess a walk, vertex-by-vertex, that gets you back to where you started: using memory to avoid going back along the most recently used edge means you must have gone around a cycle to get back where you started. Off the top of my head, I can't see a direct way to do acyclicity in NL: part of the reason that Immerman–Szelepcsényi is so important is that it lets you construct things like this much more easily. $\endgroup$ – David Richerby Oct 25 '14 at 14:49
  • $\begingroup$ Thanks, you're right. We can only guess a walk, not a cycle. Well, I was just hoping for an insightful direct construction... $\endgroup$ – john_leo Oct 25 '14 at 14:56
  • $\begingroup$ @DavidRicherby Why can't we do in following way: We fix possible lengths of cycle and try to guess them vertex by vertex. In other words, lets lenght will be $l$. Then we guess starting vertex, then guess $l$ verticles one be one. If we come back to starting node we accept. And if for any length we accepted we reject. I think that simply such algorithm is in $P^{NL}$, no $NL$. Yeah ? $\endgroup$ – Haskell Fun Aug 28 '17 at 18:12
  • $\begingroup$ @HaskellFun You seem to be proposing essentially the same algorithm as me. I'm not sure why you think it's in $\mathrm{P^{NL}}$ but not in $\mathrm{NL}$. Sure, it takes a polynomial number of steps but it only uses logarithmic space. $\endgroup$ – David Richerby Aug 28 '17 at 18:58
  • $\begingroup$ @DavidRicherby you suggested to use $coNL$. I gave $NL$ so I was think that I cheated and used class $P^{NL}$ (because I am using NL as oracle) $\endgroup$ – Haskell Fun Aug 28 '17 at 19:05
3
$\begingroup$

It's easy to see that the problem is coNL-complete.

If you could find a direct proof that ACYCLIC GRAPH is in NL, then it would be a direct proof of NL=coNL. However, as far as I know, nobody knows about a proof of this fact that does not use the inductive counting technique. See https://cstheory.stackexchange.com/questions/2145/alternate-proofs-of-immerman-szelepcsenyi-theorem and Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$.

(By the way, I find it bit easier to think about the problem "CYCLIC GRAPH" as in "graph that has a cycle"; it's easy to show that's it's NL-complete.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Ah, thanks. Good point: If we have a problem for which we can directly show that it's NL-complete and coNL-complete, then we have an alternative proof for Immerman-Szelepcsényi. That probably explains why a direct NL-proof is hard to find... $\endgroup$ – john_leo Oct 25 '14 at 15:20

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.