# Acyclic Graph in NL

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?

• 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. – David Richerby Oct 25 '14 at 14:49
• Thanks, you're right. We can only guess a walk, not a cycle. Well, I was just hoping for an insightful direct construction... – john_leo Oct 25 '14 at 14:56
• @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 ? – Haskell Fun Aug 28 '17 at 18:12
• @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. – David Richerby Aug 28 '17 at 18:58
• @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) – Haskell Fun Aug 28 '17 at 19:05

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$.