NL denotes the class of languages, which can be decided by a non-deterministic Turing machine using $O(\log n)$ work tape cells.

A language $L$ is said to be NL-hard if $\forall L' \in$ NL : $L'\leq_L L\,$ (NL-hardness)

where $\leq_L$ denotes the log-space reduction, which is also transitive.

Given a language L. Is the following claim true?

Claim: If $\overline{L}$ is NL-hard, then $L$ also NL-hard.

Given that $\overline{L}$ is NL-hard, we can log-space-reduce every problem contained in NL to $\overline{L}$, i.e. $\forall L'\in$ NL : $L'\leq_L \overline{L}$. Due to the Immerman–Szelepcsényi theorem we know that coNL = NL, but I do not know whether I can make progress with that fact.


Take some language $L'\in \text{NL}$, so since $\text{NL=coNL}$ we have $\overline{L'}\in \text{NL}$, and since $\overline{L}$ is $\text{NL}$-hard we have $\overline{L'}\leq_{log}\overline{L}$ therefore $L'\leq_{log}L$ (with the same reduction)

| cite | improve this answer | |

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.