This book is an introduction to the rapidly growing theory of P completeness — the branch of complexity theory that focuses on
identifying the “hardest” problems in the class P of problems solvable in polynomial time. P -complete problems are of interest because
they all appear to lack highly parallel solutions. That is, algorithm
designers have failed to find NC algorithms, feasible highly parallel
solutions that take time polynomial in the logarithm of the problem
size while using only a polynomial number of processors, for them.
Consequently, the promise of parallel computation, namely that applying more processors to a problem can greatly speed its solution,
appears to be broken by the entire class of P -complete problems.
This state of affairs is succinctly expressed as the following question:
Does P equal NC ?
