2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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.. $\endgroup$ – fade2black Aug 28 '17 at 21:52
  • $\begingroup$ @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 >? $\endgroup$ – MathMaster Aug 29 '17 at 18:37
  • $\begingroup$ That's right. When used as an oracle, it's like a function call and we can do whatever we want with the output. $\endgroup$ – Yuval Filmus Aug 29 '17 at 18:37
  • $\begingroup$ 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. $\endgroup$ – MathMaster Aug 29 '17 at 19:02

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.