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 '17 at 21:02
  • $\begingroup$ What makes you think it couldn't be true? Did you find a counterexample language? $\endgroup$ – fade2black Aug 23 '17 at 21:15
  • $\begingroup$ No, I didn't find an argument to convince myself. $\endgroup$ – Logic Aug 23 '17 at 21:26

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

| cite | improve this answer | |

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.