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 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.