10
$\begingroup$

If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$? I am asking this question because, for other non-deterministic classes, it seems $\mathbf{P} = \mathbf{NP}$ always establishes that they are equal to their deterministic counterparts.

$\endgroup$
15
$\begingroup$

This is an open research question. At our current state of knowledge, knowing $\mathbf{P}=\mathbf{NP}$ would neither imply $\mathbf{L}=\mathbf{NL}$ nor $\mathbf{L}\neq\mathbf{NL}$. And, conversely, knowing $\mathbf{L}=\mathbf{NL}$ or $\mathbf{L}\neq\mathbf{NL}$ wouldn't imply anything about the $\mathbf{P}$ vs $\mathbf{NP}$ question. (But it's possible that the proof of $\mathbf{L}$ vs $\mathbf{NL}$ would tell us something about $\mathbf{P}$ vs $\mathbf{NP}$ or vice-versa.)

We know $\mathbf{L}\subseteq \mathbf{NL} \subseteq \mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE} = \mathbf{NPSPACE}$, where the equality follows from Savitch's theorem. The nondeterministic version of the space hierarchy theorem says that $\mathbf{NL}\neq \mathbf{NPSPACE}$ so we know that at least one of the set inclusions must be strict. We kinda think they're all strict but our current knowledge doesn't rule out any subset of them, as long as it includes at least one between $\mathbf{NL}$ and $\mathbf{PSPACE}$.

$\endgroup$

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.