<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2012-06-22T19:35:16.650Z
Do you care about the difference between these reductions only in the context of P-completeness or also for (say) NP-completeness?
Robin Kothari
CC BY-SA 3.0
2012-06-25T03:37:51.033Z
@RobinKothari Primarily for P-completeness, but results for NP- and PSPACE-completeness would be helpful for context.
argentpepper
<cc.complexity-theory><dc.parallel-comp><reductions>
What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?
argentpepper
# What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?

(Asked by: username_0 on 2012-06-22)

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?

**Tags:** cc.complexity-theory, dc.parallel-comp, reductions

> **Comments:**
> **username_1**: Do you care about the difference between these reductions only in the context of P-completeness or also for (say) NP-completeness?  
> **username_0**: @RobinKothari Primarily for P-completeness, but results for NP- and PSPACE-completeness would be helpful for context.  

---

## 0 answers

