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?
1
-
$\begingroup$ Note that these two classes cannot even be separated by an oracle, not even L and NP; see section 3 here: lance.fortnow.com/papers/files/diag.pdf $\endgroup$– domotorpJun 9 at 21:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
answered Jun 9 at 17:00