 Pcomplete

In complexity theory, the notion of Pcomplete decision problems is useful in the analysis of both:
 which problems are difficult to parallelize effectively, and;
 which problems are difficult to solve in limited space.
Formally, a decision problem is Pcomplete (complete for the complexity class P) if it is in P and that every problem in P can be reduced to it by using an appropriate reduction.
The specific type of reduction used varies and may affect the exact set of problems. If we use NC reductions, that is, reductions which can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all Pcomplete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the weaker logspace reduction, this remains true, but additionally we learn that all Pcomplete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set Pcomplete may be smaller.
Contents
Motivation
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.
Similarly, the class L contains all problems that can be solved by a sequential computer in logarithmic space. Such machines run in polynomial time because they can have a polynomial number of configurations. It is suspected that L ≠ P; that is, that some problems that can be solved in polynomial time also require more than logarithmic space.
Similarly to the use of NPcomplete problems to analyze the P = NP question, the Pcomplete problems, viewed as the "probably not parallelizable" or "probably inherently sequential" problems, serves in a similar manner to study the NC = P question. Finding an efficient way to parallelize the solution to some Pcomplete problem would show that NC = P. It can also be thought of as the "problems requiring superlogarithmic space"; a logspace solution to a Pcomplete problem (using the definition based on logspace reductions) would imply L = P.
The logic behind this is analogous to the logic that a polynomialtime solution to an NPcomplete problem would prove P = NP: if we have a NC reduction from any problem in P to a problem A, and an NC solution for A, then NC = P. Similarly, if we have a logspace reduction from any problem in P to a problem A, and a logspace solution for A, then L = P.
Pcomplete problems
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. If the number of steps is written in binary, the problem is EXPTIMEcomplete.
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 are widely believed to be inherently sequential. These include the following problems, either as given, or in a decisionproblem form:
 Circuit Value Problem (CVP)  Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate
 Restricted Case of CVP  Like CVP, except each gate has two inputs and two outputs (F and Not F), every other layer is just AND gates, the rest are OR gates (or, equivalently, all gates are NAND gates, or all gates are NOR gates), the inputs of a gate come from the immediately preceding layer
 Linear programming  Maximize a linear function subject to linear inequality constraints
 Lexicographically First Depth First Search Ordering  Given a graph with fixed ordered adjacency lists, and nodes u and v, is vertex u visited before vertex v in a depthfirst search induced by the order of the adjacency lists?
 Context Free Grammar Membership  Given a contextfree grammar and a string, can that string be generated by that grammar?
 Hornsatisfiability: given a set of Horn clauses, is there a variable assignment which satisfies them? This is P's version of the boolean satisfiability problem.
 Game of Life  Given an initial configuration of Conway's Game of Life, a particular cell, and a time T (in unary), is that cell alive after T steps?
 LZW (algorithm) (1978 paradigm) Data Compression  given strings s and t, will compressing s with an LZ78 method add t to the dictionary? (Note that for LZ77 compression such as gzip, this is much easier, as the problem reduces to "Is t in s?".)
 Type inference for partial types  Given an untyped term from the lambda calculus, determine whether this term has a partial type.
In order to prove that a given problem is Pcomplete, one typically tries to reduce a known Pcomplete problem to the given one.
In 1999, JinYi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse language that is Pcomplete, then L = P.^{[1]}
Problems not known to be Pcomplete
Some problems are not known to be either NPhard or in 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 numbers, and determining what answer the extended Euclidean algorithm would return when given two numbers.
Notes
 ^ Cai, JinYi; Sivakumar, D. (1999), "Sparse hard sets for P: resolution of a conjecture of Hartmanis", Journal of Computer and System Sciences 58 (2): 280–296, doi:10.1006/jcss.1998.1615, http://citeseer.ist.psu.edu/501645.html
References
 Greenlaw, Raymond, James Hoover, and Walter Ruzzo. 1995. Limits To Parallel computation; PCompleteness Theory. ISBN 0195085914. — Develops the theory, then catalogs 96 PComplete problems.
 Satoru Miyano, Shuji Shiraishi, and Takayoshi Shoudai. A List of PComplete Problems. Kyushu University, RIFISTRCS17. December 1990.
Important complexity classes (more) Classes considered feasible Classes suspected to be infeasible UP • NP (NPcomplete · NPhard · coNP · coNPcomplete) • AM • PH • PP • #P (#Pcomplete) • IP • PSPACE (PSPACEcomplete)Classes considered infeasible Class hierarchies Families of complexity classes Categories: Complexity classes
Wikimedia Foundation. 2010.