5
$\begingroup$

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?

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

0

Reset to default

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.