We know that coNL = NL. But, is this also true?

If A is NL-complete then complement of A is also NL-complete?

I don't see a reason for that it could be true.

  • $\begingroup$ If problem $X$ is complete for class $A$, isn't $X$ is $coA$-hard? $\endgroup$
    – rus9384
    Aug 23, 2017 at 21:02
  • $\begingroup$ What makes you think it couldn't be true? Did you find a counterexample language? $\endgroup$
    – fade2black
    Aug 23, 2017 at 21:15
  • $\begingroup$ No, I didn't find an argument to convince myself. $\endgroup$
    – Logic
    Aug 23, 2017 at 21:26

1 Answer 1


Start with the definition of $coNL$. $$coNL = \{A\mid \overline{A} \in NL\}$$ Since $NL=coNL$, every $coNL$-complete language is $NL$-complete as well. Let $A$ be a $NL$-complete problem. Then $$\forall B \in NL,B \leq_L A$$ or equivalently $$x \in B \Longleftrightarrow f(x) \in A, \text{ where } f \text{is logspace computable}$$ $$x \notin B \Longleftrightarrow f(x) \notin A, \text{ where } f \text{is logspace computable}$$ $$x \in \overline{B} \Longleftrightarrow f(x) \in \overline{A}, \text{ where } f \text{is logspace computable}$$

and so $$\forall \overline{B} \in coNL,\overline{B} \leq_L \overline{A}$$ This shows that $\overline{A} $ is $coNL$-complete and hence $NL$-complete (since $coNL=NL)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.