[Solved]: Acyclic Graph in NL

Problem Detail: 

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?

Asked By : john_leo

Answered By : sdcvvc

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 http://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.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32296