5
$\begingroup$

What would be some implications of $NL$$=P$? Would it be possible to get recommendations on good sources/papers I can read to learn more about this? Thank you

$\endgroup$
  • 1
    $\begingroup$ No, Non deterministic logarithmic space. I believe implications of P=NP is widely available. $\endgroup$ – user86212 Mar 31 '18 at 23:49
  • $\begingroup$ That's what I thought, but someone tried to 'correct' this into 'NP'. Let me clarify this. $\endgroup$ – Discrete lizard Apr 1 '18 at 6:53
  • 1
    $\begingroup$ You might want to take a look at consequences of $NC=P$. This is a weaker statement, but more widely discussed (parallelism of P-complete problems). $\endgroup$ – Ariel Apr 1 '18 at 15:11
1
$\begingroup$

$NL = P$ means that every language in $P$ can be decided by a nondeterministic Turing machine using at most $O(\log n)$ space, where $n$ is the size of the input.

Savitch's theorem states for all $f(n) \in \Omega(\log n)$: $NSPACE(f(n))\subseteq SPACE(f(n)^2)$.

Therefore $NL = P$ implies that every language in $P$ can be decided by a deterministic Turing machine using at most $O((\log n)^2)$ space.

$\endgroup$
  • $\begingroup$ This is true but I think the question is really looking for more just "If NL=P then everything fact about NL is also true of P." $\endgroup$ – David Richerby Mar 28 '19 at 12:59

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.