2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The definition of coNL is: all problems whose complement is in NL. $\endgroup$ – Yuval Filmus Oct 24 '18 at 5:04
  • $\begingroup$ You can't "flip the result" in nondeterministic models. For example, it is known that the r.e. languages are not closed under complement. $\endgroup$ – Yuval Filmus Oct 24 '18 at 5:04
  • $\begingroup$ @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}$. $\endgroup$ – user869887 Oct 24 '18 at 6:38
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – user869887 Oct 24 '18 at 7:47
  • $\begingroup$ It's hard for me to answer your first question, since I don't know which definition Sipser uses. But the definition is probably very similar, albeit it might look different. $\endgroup$ – Yuval Filmus Oct 24 '18 at 7:52
  • $\begingroup$ For the second question, see my updated answer. $\endgroup$ – Yuval Filmus Oct 24 '18 at 7:55
  • $\begingroup$ 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 : ) $\endgroup$ – user869887 Oct 24 '18 at 8:09

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.