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

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.

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

## 1 Answer

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