Researchers have developed a theory of the parallel complexity of
computational problems analogous to the theory of NP-completeness. A
problem is said to belong to the class *NC* (Nick's Class) if it
can be solved in time polylogarithmic in the size of the problem using
at most a polynomial number of processors. The class *NC* in parallel
complexity theory plays the role of *P* in sequential complexity,
i.e., the problems in *NC* are thought to be tractable in parallel.
Examples of problems in *NC* include sorting, finding minimum-cost
spanning trees, and finding convex hulls. A problem is said to be
*P*-complete if it can be solved in polynomial time and if its
inclusion in *NC* would imply that *NC = P*. Hence, the notion of
*P*-completeness plays the role of *NP*-completeness in sequential
complexity. (And few believe that *NC = P*.) Examples of
*P*-complete problems include finding a maximum flow and finding a
lexicographically minimum independent set of nodes in a graph. Much
early work in parallel algorithms aimed at showing that certain
problems belonged to the class *NC* (without considering the issue of
efficiency). This work tapered off, however, as the importance of
work-efficiency became evident. Also, even if a problem is
*P*-complete, there may be efficient (but not necessarily
polylogarithmic time) parallel algorithms for solving it. For
example, several efficient and highly parallel algorithms are known
for solving the maximum flow problem, which is *P*-complete.

Guy Blelloch, blelloch@cs.cmu.edu