1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ Isn't it trivial? Did you try to prove yourself? What confuses you? $\endgroup$
    – fade2black
    Aug 22, 2017 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, 2017 at 12:57

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oh, yeah. It is trival in the fact :) $\endgroup$
    – Logic
    Aug 22, 2017 at 20:39
2
$\begingroup$

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

$\endgroup$

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.