The specific type of reduction used varies and may affect the exact set of problems.
If we use NC reductions, that is, reductions which can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all P-complete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the stronger log-space reduction, this remains true, but additionally we learn that all P-complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set P-complete may be smaller.
The class P, typically taken to consist of all the "tractable" problems for a sequential computer, contains the class NC, which consists of those problems which can be efficiently solved on a parallel computer.
It is not known whether NC = P. In other words, it is not known whether there are any tractable problems that are inherently sequential.
Just as it is widely suspected that P does not equal NP, so it is widely suspected that NC does not equal P. Similarly, the class L contains all problems that can be solved by a sequential computer in logarithmic space.
It is suspected that L ≠ P; that is, that some problems that can be solved in polynomial time also require more than logarithmic space.
steps if and only if x is in L. Clearly, if we can parallelize a general simulation of a sequential computer (ie.
This problem illustrates a common trick in the theory of P-completeness.
We aren't really interested in whether a problem can be solved quickly on a parallel machine.
Many other problems have been proved to be P-complete, and therefore are widely believed to be inherently sequential.
These include the following problems which are P-complete under at least logspace reductions, either as given, or in a decision-problem form: Most of the languages above are P-complete under even stronger notions of reduction, such as uniform
In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse language that is P-complete, then L = P.[1] P-complete problems may be solvable with different time complexities.
For instance, the Circuit Value Problem can be solved in linear time by a topological sort.