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:

• $PATH$ is $NL$-complete

• so $\overline{PATH}$ is $coNL$-hard

• and $\overline{PATH}$ is in $NL$

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

$\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^$.

Now I can answer your questions:

-
$\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}}$.

-
Flipping the output value of a nondeterministic machine does not result in complementing the accepted language.

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.

StackExchange Computer Science Q#99007, answer score: 3