Redirected from PComplete
The class P, typically taken to consist of all the "tractable" problems for a sequential computer, contains the class NC, which consists of those problems which can be efficiently solved on a parallel computer. This is because parallel computers can be simulated on a sequential machine. It is not known whether NC=P. In other words, it is not known whether there are any tractable problems that are inherently sequential. Just as it is widely suspected that P does not equal NP, so it is widely suspected that NC does not equal P.
The class NPcomplete, which can be thought of as containing the "probably intractable" problems, is introduced to analyze the P=NP question, and the class Pcomplete, which can be thought of as containing the "probably not parallelizable" or "probably inherently sequential" problems, serves in a similar manner to study the NC=P question. The suspicion that NC ≠ P could be disproved by finding an efficient way to parallelize the solution to some Pcomplete problem.
The most basic Pcomplete problem is this: given a Turing machine, an input for that machine, and a number T (written in unary), does that machine halt on that input within the first T steps? It is clear that this problem is Pcomplete: if we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so is every other problem in P.
This problem illustrates a common trick in the theory of Pcompleteness. We aren't really interested in whether a problem can be solved quickly on a parallel machine. We're just interested in whether a parallel machine solves it much more quickly than a sequential machine. Therefore, we have to reword the problem so that the sequential version is in P. That is why this problem required T to be written in unary. If a number T is written as a binary number (a string of n ones and zeros, where n=log(T)), then the obvious sequential algorithm can take time 2^{n}. On the other hand, if T is written as a unary number (a string of n ones, where n=T), then it only takes time n. By writing T in unary rather than binary, we have reduced the obvious sequential algorithm from exponential time to linear time. That puts the sequential problem in P. Then, it will be in NC if and only if it is parallelizable.
Many other problems have been proved to be Pcomplete, and therefore widely believed to be inherently sequential. These include the following problems, either as given, or in a decisionproblem form:
In order to prove that a given problem is Pcomplete, one typically tries to reduce a known Pcomplete problem to the given one, using an efficient parallel algorithm.
Some problems are not known to be either NPcomplete or P. These problems (e.g. factoring) are suspected to be difficult. Similarly there are problems that are not known to be either Pcomplete or NC, but are thought to be difficult to parallelize. Examples include the decision problem forms of finding the greatest common divisor of two binary numbers, and determining what answer the extended Euclidean algorithm would return when given two binary numbers.
For more information:
Search Encyclopedia

Featured Article
