What is P-completeness?
P-complete problems are the hardest problems in P to parallelize. Just as NP-complete problems are believed to have no efficient sequential algorithms, P-complete problems are believed to have no efficient parallel algorithms, and are said to be inherently sequential.
More precisely, a problem is P-complete if:
- It is in P (solvable in polynomial time)
- Every other problem in P can be reduced to it using an NC reduction. NC is the class of problems/algorithms which use polylogarithmic time and polynomially many processors.
If any P-complete problem can be solved efficiently in parallel (in NC), then all problems in P can be solved efficiently in parallel — that is, P = NC.
About This Compendium
This compendium uses the following as a main reference:
Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press.
These references cover foundational results and broad problem catalogs across circuit complexity, graph theory, logic, algebra, and more.
Contributing
This is an open-source project! You can contribute by:
- Adding new P-complete problems
- Improving problem descriptions and remarks
- Fixing errors or adding references
See our Contributing Guide for details.
Base P-complete problems
- Circuit Value Problem (CVP) — The foundational P-complete problem, analogous to SAT for NP-completeness
- Generic Machine Simulation Problem (GMSP) — The base problem of simulating a Turing machine efficiently in parallel