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?
0
$\begingroup$
$\endgroup$
-
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
2
$\begingroup$
$\endgroup$
If the language $A$ is $NL$-complete then
- $A \in NL$
- 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.
2
$\begingroup$
$\endgroup$
Yes, if a problem is $coNL-complete$ it's $NL-complete$.
Take a language $L$ which is $coNL-complete$.
- By theorem (that you mentioned) there exist a TM which accepts it in $NL$ so $L \in NL$.
- 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
