# Recognizing strongly connected digraphs in NL

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.