This homework solution gives a proof that $L = \{G \mid \text{G is strongly connected directed graph}\} \in N\mathcal{L}$. One suggested way to proof that $L \in N\mathcal{L}$ by proving that $\bar{L} = \{G \mid \text{G is not strongly connected} \} \in NL$ and then using the fact $NL = coNL$.

The tutorial uses the following algorithm for $\bar{L}$:

  1. Nondeterministically select two nodes $(a,b)$
  2. Run $PATH(a,b)$. If it rejects, then the graph is not strongly connected, so accept. Otherwise reject.

Since $PATH$ itself is a nondeterministic algorithm (or rather, we have to use a nondeterministic algorithm to still be $N\mathcal{L}$, it is not clear to me why this is correct. Why is it okay to invert the answer of $PATH$ in this case?

For example, assume our nondeterministic choices wrongly lead us to believe there is no path between $a$ and $b$, then this nondeterministic branch would accept (which means our whole TM $M$ would accept, because there is one accepting branch). But if there is also a branch of $PATH$, then our graph $G$ might actually be strongly connected and $M$ will return a wrong answer by accepting.


Because nondeterministic space classes are closed under complementation by the Immerman–Szelepcsényi theorem. So, you can't literally just invert the answer from $\text{PATH}(a,b)$ but the fact that there is an $\mathrm{NL}$ algorithm for $\text{PATH}(a,b)$ implies that there is also an $\mathrm{NL}$ algorithm for $\text{NOT-PATH}(a,b)$, and you use that.


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.