P-complete

In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction.

The notion of P-complete decision problems is useful in the analysis of which problems are difficult to parallelize effectively and which problems are difficult to solve in limited space, specifically when stronger notions of reducibility than polytime-reducibility are considered.

The specific type of reduction used varies and may affect the exact set of problems. Generically, reductions stricter than polynomial-time reductions are used, since all languages in P (except the empty language and the language of all strings) are P-complete under polynomial-time reductions. If we use NC reductions, that is, reductions that 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.