# If problem is coNL-complete, is it NL-complete

We know from Immerman-Szelepcsényi theorem that $coNL=NL$. But, what about: If problem is $coNL\text{-}complete$, is it $NL\text{-}complete$? And why?

• Isn't it trivial? Did you try to prove yourself? What confuses you? – fade2black Aug 22 '17 at 20:25
• You can see *-complete as a function that takes a class $C$ of problems and returns the class $C'$ of $C-complete$ problems, i.e., $\operatorname{Complete}(C):=\{P : P \in C\text{ and }P\text{ is }C\text{-hard}\}$. Your question becomes: Since $coNL = NL$, do we have $\operatorname{Complete}(coNL)=\operatorname{Complete}(NL)$ to which the answer is obviously yes: You applied the same function to the same argument so the result will be the same. – xavierm02 Aug 23 '17 at 12:57

If the language $A$ is $NL$-complete then

1. $A \in NL$
2. Each problem in $NL$ is logspace reducible to $A$

Since $coNL = NL$ each problem in $coNL$ is logspace reducible to $A$ as well. Thus $A$ is $coNL$-complete.

• Oh, yeah. It is trival in the fact :) – Logic Aug 22 '17 at 20:39

Yes, if a problem is $coNL-complete$ it's $NL-complete$.

Take a language $L$ which is $coNL-complete$.

1. By theorem (that you mentioned) there exist a TM which accepts it in $NL$ so $L \in NL$.
2. Now, take a language $L_1 \in NL$. By theorem $L_1 \in coNL$ and by $L$ being $coNL-Hard$ there exist a log-space reduction $L_1 <_L L$. So, $L$ is $NL-Hard$.

Therefore, $L$ is $NL-complete$.

The theorem : Immerman–Szelepcsényi theorem