<p>As far as I know, the general consensus is that NLOGSPACE (NL) is different from P. Indeed, it is believed that &quot;Nick's Class&quot; NC (which contains NLOGSPACE) is different from P. The main reason is that people believe some computational processes are inherently sequential: that is, they believe parallelization cannot speed up a computation by more than (say) a polynomial factor. For example, if NL = P, then since NL is in NC^2, and Circuit Evaluation is P-complete, we would have that <em>every</em> poly(n)-size circuit of depth n can be converted into a polynomially-larger circuit of depth only O(log^2 n). This looks too good to be true.</p>
<p>As for evidence possibly in favor of NL = P: it is known that P=ALOGSPACE (alternating logspace, the generalization of NL where each state can be either &quot;existential&quot; or &quot;universal&quot;) and we know NL=coNL, so NL^(NL)=NL (for some reasonable definition of NL^(NL)) and &quot;ALOGSPACE with a constant number of alternations per path&quot; equals NL. However, this evidence looks weak compared to the intuition of the previous paragraph.</p>

CC BY-SA 4.0
2023-06-09T17:00:10.923Z
2023-06-09T17:00:10.923Z
Ryan Williams
<p>As it stands, we know that NL is a subset of P, but we do not know if it is a proper subset or not. With that said, what is the general consensus? Do the majority think that NL = P or not? What would be some strong indications for one conclusion over another?</p>

CC BY-SA 4.0
2023-06-09T21:21:44.587Z
Note that these two classes cannot even be separated by an oracle, not even L and NP; see section 3 here: https://lance.fortnow.com/papers/files/diag.pdf
domotorp
<cc.complexity-theory>
What is the general consensus on the NL vs P question?
Ashvin jagadeesan
# What is the general consensus on the NL vs P question?

(Asked by: username_0 on 2023-06-09)

As it stands, we know that NL is a subset of P, but we do not know if it is a proper subset or not. With that said, what is the general consensus? Do the majority think that NL = P or not? What would be some strong indications for one conclusion over another?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Note that these two classes cannot even be separated by an oracle, not even L and NP; see section 3 here: https://lance.fortnow.com/papers/files/diag.pdf  

---

## 1 answers

### Answer by username_2 on 2023-06-09. Score: 13

As far as I know, the general consensus is that NLOGSPACE (NL) is different from P. Indeed, it is believed that "Nick's Class" NC (which contains NLOGSPACE) is different from P. The main reason is that people believe some computational processes are inherently sequential: that is, they believe parallelization cannot speed up a computation by more than (say) a polynomial factor. For example, if NL = P, then since NL is in NC^2, and Circuit Evaluation is P-complete, we would have that *every* poly(n)-size circuit of depth n can be converted into a polynomially-larger circuit of depth only O(log^2 n). This looks too good to be true.

As for evidence possibly in favor of NL = P: it is known that P=ALOGSPACE (alternating logspace, the generalization of NL where each state can be either "existential" or "universal") and we know NL=coNL, so NL^(NL)=NL (for some reasonable definition of NL^(NL)) and "ALOGSPACE with a constant number of alternations per path" equals NL. However, this evidence looks weak compared to the intuition of the previous paragraph.


---

