# how does $PATH$ being $NL$-complete help to prove $NL = coNL$

There is a proof in Sipser showing that $$NL = coNL$$ (theorem 8.27 in the 3rd edition).

In the proof idea, the first sentence is: "We show that $$\overline{PATH}$$ is in $$NL$$, and thereby establish that every problem in $$coNL$$ is also in $$NL$$, because $$PATH$$ is $$NL$$-complete." I'm having trouble understanding this.

Sipser did not elaborate on this, but it sounds like the logic behind this sentence is:

1. $$PATH$$ is $$NL$$-complete
2. so $$\overline{PATH}$$ is $$coNL$$-hard
3. and $$\overline{PATH}$$ is in $$NL$$
4. so $$coNL \subseteq NL$$

If so, why can we get 2 from 1?

More generally, since $$PATH$$ can be decided in $$NL$$ (Sipser example 8.19), why can't we just flip the result to decide $$\overline{PATH}$$ directly?

• The definition of coNL is: all problems whose complement is in NL. Oct 24 '18 at 5:04
• You can't "flip the result" in nondeterministic models. For example, it is known that the r.e. languages are not closed under complement. Oct 24 '18 at 5:04
• @YuvalFilmus Thanks for the comments. 1. Are you saying we can reduce from $\overline{L}$ to $L$, then $L$ to $PATH$, then $PATH$ to $\overline{PATH}$? Or the fact that $L$ is reducible to $PATH$ means $\overline{L}$ is reducible to $\overline{PATH}$? 2. I understand why such behavior is incorrect for $NP$ and $coNP$, as there're certificates and verifiers involved, but I still can't see why it's the case here. Say there is no path from $s$ to $t$ in $G$, then a decider for $PATH$ will say no, and by reversing the output, the answer is valid for $\overline{PATH}$. Oct 24 '18 at 6:38

$$\mathsf{NL}$$ consists of all languages accepted by nondeterministic Turing machines using logarithmic space. One way to think of such machines is as follows:

• The input is written on a read-only input tape.
• There are one or more work tapes of logarithmic size.
• There is a read-only oracle tape on which the head is constrained to only move to the right.

We can think of each such machine as computing a Boolean function on two arguments: $$x$$, which is the actual input, and $$y$$, which is the initial contents of the oracle tape. Such a machine $$M$$ nondeterministically computes the language $$L(M)$$ given by: $$x \in L(M) \Longleftrightarrow \exists y \text{ s.t. M(x,y) accepts}.$$ In other words, a language $$L$$ is in $$\mathsf{NL}$$ if there exists a logspace Turing machine $$M$$ with an auxiliary oracle input such that $$x \in L \Longleftrightarrow \exists y \text{ s.t. M(x,y) accepts}.$$

A language is in $$\mathsf{coNL}$$ if its complement is in $$\mathsf{NL}$$. Equivalently, a language $$L$$ is in $$\mathsf{coNL}$$ if there exists a logspace Turing machine $$M$$ with an auxiliary oracle input such that $$x \notin L \Longleftrightarrow \exists y \text{ s.t. M(x,y) rejects}.$$ Equivalently, $$x \in L \Longleftrightarrow \forall y \text{ M(x,y) accepts}.$$

Suppose now that $$L$$ is in $$\mathsf{NL}$$, say $$L = L(M)$$, and let $$M'$$ be obtained from $$M$$ by complementing the output. Then $$x \in L(M') \Longleftrightarrow \exists y \text{ s.t. M'(x,y) accepts} \Longleftrightarrow \exists y \text{ s.t. M(x,y) rejects}.$$ As you can see, $$L(M')$$ isn't necessarily the complement of $$L(M)$$. Indeed, given any machine $$M$$, we can come up with another machine $$\tilde{M}$$ such that $$L(M) = L(\tilde{M})$$, but $$\tilde{M}(x,y_0)$$ always rejects, for some fixed $$y_0$$ (for example, $$\tilde{M}(x,0\Sigma^*)$$ always rejects, and $$\tilde{M}(x,1y) = M(x,y)$$). In this case, $$L(\tilde{M}') = \Sigma^*$$.

• $$\overline{\mathsf{PATH}} \in \mathsf{coNL}$$ since $$\mathsf{PATH} \in \mathsf{NL}$$ and by definition $$\mathsf{coNL}$$ consists of the complements of all languages in $$\mathsf{NL}$$.
• Furthermore, $$\overline{\mathsf{PATH}}$$ is $$\mathsf{coNL}$$-hard because $$\mathsf{PATH}$$ is $$\mathsf{NL}$$-hard. Indeed, suppose that $$L \in \mathsf{coNL}$$. Then $$\overline{L} \in \mathsf{NL}$$. Since $$\mathsf{PATH}$$ is $$\mathsf{NL}$$-hard, there is a logspace reduction $$f$$ such that $$x \in \overline{L}$$ iff $$f(x) \in \mathsf{PATH}$$. Thus $$x \in L$$ iff $$f(x) \in \overline{\mathsf{PATH}}$$, and so $$f$$ also reduces $$L$$ to $$\overline{\mathsf{PATH}}$$.
Elaborating on the second point, for some nondeterministic complexity classes $$\mathsf{X}$$, it is known that $$\mathsf{X} \neq \mathsf{coX}$$. The simplest example is $$\mathsf{RE} \neq \mathsf{coRE}$$: the halting problem is in $$\mathsf{RE}$$ but not in $$\mathsf{coRE}$$. Therefore $$\mathsf{NL} = \mathsf{coNL}$$ is a nontrivial statement.
• Thank you! I think I understand the second point now. Out of curiosity, if we don't have the oracle tape (as $NL$ is defined in Sipser), would it be much more difficult to prove this point? As for the first point, just to double check, you are saying $\overline{PATH}$ is $coNL$-hard because $PATH$ is $NL$-complete AND $\overline{PATH} \in coNL$? Oct 24 '18 at 7:47
• Sipser's definition of $NL$ is indeed similar. It has only one read-only input tape and one read-write work tape. I suppose arguing with this definition is non-trivial and my original question is solved now, but you can answer that question if you want : ) Oct 24 '18 at 8:09