# Polynomially many times launch $NL$ machine - is it in $NL$? On example of ACYCLIC

Lets consider $$ACYCLIC = \{\langle G \rangle | G \text{ is acyclic}\}$$
We are going to prove that $ACYCLIC\in NL$. I know that the easiest approach for this task is to use the fact that $coNL=NL$. However, I wonder if correct answer is following approach:

The idea is to check each existence of each length of cycle. Let $n$ will be number of cycles.

    for l = 1..n
is_cycle = non-deterministally check if there exists cycle of length l
if (is_cycle == "yes")
then return "no"
return "yes"// graph is acyclic because there is no cycle of length 1..n


Is it correct approach in $NL$?

You cannot implement this part in NL:

nondeterministically check something

if yes, return no

Consider the following analogy: the language $K$ of all Turing machines that halt is recursively enumerable but its negation isn't. That is, $K$ is accepted by some nondeterministic Turing machine, but its negation cannot be accepted by any nondeterministic Turing machine. This means that you provably cannot implement the following using nondeterminism:

nondeterministically check if the given Turing machine halts

if yes, return no

Your idea suffers from the same problem.

Here is a different angle. The following algorithm checks nondeterministically that $s$ and $t$ are connected:

guess a path $w$ from $s$ to $t$

verify that $w$ is a path; if so, output yes, otherwise, output no

The semantics of this algorithm are as follows:

1. If there is some witness that causes the algorithm to output yes, then the input is a yes input.

2. If all witnesses cause the algorithm to output no, then the input is a no input.

What you are trying to do is as follows:

guess a path $w$ from $s$ to $t$

verify that $w$ is a path; if so, output no, otherwise, output yes

All inputs are yes instances in this case, since there is always some witness $w$ that isn't a path from $s$ to $t$.

In order to check that there is no path, you would have to do the following:

go over all possible paths $w$ from $s$ to $t$

if none of them works, output yes, otherwise, output no

Unfortunately, this doesn't describe a nondeterministic Turing machine.

• I think that it would be great to create a reference question concerning how NDTM and DTM work, different but equivalent models, wrong designs of NDTMs, etc.. – fade2black Aug 28 '17 at 21:52
• @YuvalFilmus: In other words, we can't negate answer of nondeterministal machine, yeah ? However, when NTM is treated as oracle that we can negate its answer. yeah >? – MathMaster Aug 29 '17 at 18:37
• That's right. When used as an oracle, it's like a function call and we can do whatever we want with the output. – Yuval Filmus Aug 29 '17 at 18:37
• Oh, so $w$ is witness. The good idea is always assign result of NTM to $w$ and then conisder when $w$ can be accepted and when rejected. – MathMaster Aug 29 '17 at 19:02