next up previous
Next: Current and Future Directions Up: Parallel Algorithms Previous: Algorithmic Techniques

Parallel Complexity Theory

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,