In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction.

The notion of P-complete decision problems is useful in the analysis of which problems are difficult to parallelize effectively and which problems are difficult to solve in limited space, specifically when stronger notions of reducibility than polytime-reducibility are considered.

The specific type of reduction used varies and may affect the exact set of problems. Generically, reductions stricter than polynomial-time reductions are used, since all languages in P (except the empty language and the language of all strings) are P-complete under polynomial-time reductions. If we use NC reductions, that is, reductions that can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all P-complete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the stronger log-space reduction, this remains true, but additionally we learn that all P-complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set P-complete may be smaller.

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 that 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 only have a polynomial number of different 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 NP-complete problems to analyze the P = NP question, the P-complete 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 P-complete problem would show that NC = P. It can also be thought of as the "problems requiring superlogarithmic space"; a log-space solution to a P-complete problem (using the definition based on log-space reductions) would imply L = P.

The logic behind this is analogous to the logic that a polynomial-time solution to an NP-complete 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 log-space reduction from any problem in P to a problem A, and a log-space solution for A, then L = P.

Reductions

There are many different many-one reductions used when defining P-completeness, with variable strengths.

At the lowest level is NC<sup>1</sup>-reduction, then L-reduction, then NC<sup>2</sup>-reduction, NC<sup>3</sup>-reduction, and so on. Their union is NC-reduction. They are ordered since <math>\mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NC}^2 \subseteq \mathsf{NC}^3 \subseteq \dots \subseteq \mathsf{NC}</math>.

For NC<sup>k</sup>-reduction and NC-reduction, uniformity is imposed, because the intention of P-completeness theory is to prove upper bounds. Non-uniformity is useful for proving lower bounds, but for upper bounds, non-uniformity is unsatisfactory, since they are too powerful for this purpose. The standard uniformity condition is L-uniformity, meaning that the circuit family should be constructable by a Turing machine, such that given <math>1^n</math> as input, it outputs a description of the <math>n</math>-th circuit using <math>O(\log n)</math> working tape.

  • Context free grammar membership – given a context-free grammar and a string, can that string be generated by that grammar?
  • Horn-satisfiability – given a set of Horn clauses, is there a variable assignment that 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.

Most of the languages above are P-complete under even stronger notions of reduction, such as uniform <math>AC^0</math> many-one reductions, DLOGTIME reductions, or polylogarithmic projections.

In order to prove that a given problem in P is P-complete, one typically tries to reduce a known P-complete problem to the given one.

In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse language that is P-complete, then L&nbsp;=&nbsp;P.

P-complete problems may be solvable with different time complexities. For instance, the circuit value problem can be solved in linear time by a topological sort. Of course, because the reductions to a P-complete problem may have different time complexities, this fact does not imply that all the problems in P can also be solved in linear time.

Notes