# What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?

The $\mathsf{P}$-complete problems can be considered "inherently sequential". $\mathsf{P}$-completeness may be defined using either $\mathsf{NC}$ reductions or $\mathsf{L}$ reductions.

Since $\mathsf{L}\subseteq\mathsf{NL}\subseteq\mathsf{NC^2}\subseteq\mathsf{NC}\subseteq\mathsf{P}$, an $\mathsf{NC}$ reduction should be at least as powerful as an $\mathsf{L}$ reduction. What separations or equivalences are known between these two types of reductions?

• Do you care about the difference between these reductions only in the context of P-completeness or also for (say) NP-completeness? – Robin Kothari Jun 22 '12 at 19:35
• @RobinKothari Primarily for P-completeness, but results for NP- and PSPACE-completeness would be helpful for context. – argentpepper Jun 25 '12 at 3:37