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?

  • 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$ 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$ Jun 25, 2012 at 3:37


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.