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?

  • 1
    $\begingroup$ Isn't it trivial? Did you try to prove yourself? What confuses you? $\endgroup$
    – fade2black
    Aug 22 '17 at 20:25
  • $\begingroup$ 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. $\endgroup$
    – 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.

  • $\begingroup$ Oh, yeah. It is trival in the fact :) $\endgroup$
    – 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


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.