Editing P-complete

{{Short description|Class in computational complexity theory}}
In [[computational complexity theory]],  a [[decision problem]] is '''P-complete''' ([[complete (complexity)|complete]] for the complexity class [[P (complexity)|'''P''']]) if it is in '''P''' and every problem in '''P''' can be [[Reduction (complexity)|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,
* 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 stronger 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 (complexity)|NC]]''' reductions, that is, reductions which 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'''&nbsp;≠&nbsp;'''P'''. If we use the stronger [[log-space reduction]], this remains true, but additionally we learn that all '''P'''-complete problems lie outside [[L (complexity)|L]] under the weaker unproven assumption that '''L'''&nbsp;≠&nbsp;'''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 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'''&nbsp;=&nbsp;'''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 (complexity)|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'''&nbsp;≠&nbsp;'''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'''&nbsp;=&nbsp;'''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'''&nbsp;=&nbsp;'''P''' question. Finding an efficient way to parallelize the solution to some '''P'''-complete problem would show that '''NC'''&nbsp;=&nbsp;'''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'''&nbsp;=&nbsp;'''P'''.

The logic behind this is analogous to the logic that a polynomial-time solution to an '''NP'''-complete problem would prove '''P'''&nbsp;=&nbsp;'''NP''': if we have a '''NC''' reduction from any problem in '''P''' to a problem A, and an '''NC''' solution for A, then '''NC'''&nbsp;=&nbsp;'''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'''&nbsp;=&nbsp;'''P'''.

== Reductions ==
There are many [[many-one reduction]] used when defining P-completeness, with variable strengths.<ref name=":0">{{Cite book |last=Greenlaw |first=Raymond |title=Limits to parallel computation: P-completeness theory |last2=Hoover |first2=H. James |last3=Ruzzo |first3=Walter L. |date=1995 |publisher=Oxford University Press |isbn=978-0-19-508591-4 |location=New York}}</ref>{{Pg|location=Section 3.3}}

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.<ref name=":0" />

Given two languages <math>L, L'</math>, define <math>L \leq_m^{\mathsf{NC}^k} L' </math> iff there exists a '''L'''-uniform '''NC'''<sup>k</sup> boolean circuit family that together computes a function <math>f: \{0, 1\}^* \to \{0, 1\}^*
 </math>, such that <math>x \in L </math> iff <math>f(x) \in L' </math>.

Define <math>L \leq_m^{\mathsf{NC}} L' </math> iff <math>L \leq_m^{\mathsf{NC}^k} L' </math> for some <math>k \geq 1 </math>.

Define <math>L \leq_m^{\mathsf{L}} L' </math> iff there exists a function <math>f: \{0, 1\}^* \to \{0, 1\}^*
 </math> that is [[Log-space reduction|implicitly logspace computable]], such that <math>x \in L </math> iff <math>f(x) \in L' </math>.

=== P-complete ===
Define a language <math>L'</math> to be '''P'''-complete relative to '''NC'''<sup>k</sup>-reduction iff for any language <math>L'</math> in '''P''', <math>L \leq_m^{\mathsf{NC}^k} L' </math>. Similarly for the other cases. 

Usually for '''P'''-completeness, '''NC'''-reduction is meant by default, though many results in the literature concerning '''P'''-completeness still holds even under the strongest assumption of '''NC'''<sup>1</sup>-reduction.

P-completeness is usually used thus: First, a problem is shown to be '''P'''-complete relative to '''NC'''<sup>k</sup>-reduction. Next, assuming that the '''L'''-uniform '''NC'''<sup>k</sup> complexity class is strictly smaller than the '''P''' class, one immediately conclude that all '''P'''-complete and '''P'''-hard problems (assuming the same reduction type) are impossible to solve by  '''L'''-uniform '''NC'''<sup>k</sup> circuit families. In other words, such problems cannot be parallelized, for a certain sense of "parallelization".

== P-complete problems ==

The most basic '''P'''-complete problem under logspace many-one reductions is following: given a [[Turing machine]] <math>M</math>, an input for that machine x, and a number ''T'' (written in [[unary numeral system|unary]]), <math>\langle M,x,T \rangle</math> does that machine halt on that input within the first ''T'' steps?  For any x in <math>L</math> in P, output the encoding of the Turing machine which accepts it in polynomial-time, the encoding of x itself, and a number of steps <math>T=p(|x|)</math> corresponding to the p which is there polynomial-time bound on the operation of the Turing Machine <math>M_L</math> deciding <math>L</math>, <math>\langle M,x,p(|x|) \rangle</math>. The machine M halts on x within <math>p(|x|)</math> steps if and only if x is in L. Clearly, if we can parallelize a general simulation of a sequential computer (ie. The Turing machine simulation of a Turing machine), 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 [[EXPTIME-complete]].
This problem illustrates a common trick in the theory of '''P'''-completeness.  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 numeral system|binary]] number (a string of ''n'' ones and zeros, where ''n''&nbsp;=&nbsp;log&nbsp;''T''), then the obvious sequential algorithm can take time 2<sup>''n''</sup>.  On the other hand, if ''T'' is written as a unary number (a string of ''n'' ones, where ''n''&nbsp;=&nbsp;''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 '''P'''-complete, and therefore are widely believed to be inherently sequential.  These include the 
following problems which are '''P'''-complete under at least logspace reductions, either as given, or in a decision-problem form:
* [[Circuit Value Problem]] (CVP) – Given a [[boolean circuit|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 theory|graph]] with fixed ordered adjacency lists, and nodes ''u'' and ''v'', is vertex ''u'' visited before vertex ''v'' in a depth-first search induced by the order of the adjacency lists?<ref>{{Cite journal |last=Cook |first=Stephen A. |date=1985-01-01 |title=A taxonomy of problems with fast parallel algorithms |url=https://www.sciencedirect.com/science/article/pii/S0019995885800413 |journal=Information and Control |series=International Conference on Foundations of Computation Theory |volume=64 |issue=1 |pages=2–22 |doi=10.1016/S0019-9958(85)80041-3 |issn=0019-9958}}</ref>
* 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 clause]]s, 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 [[type theory|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'''.<ref>{{Citation | last = Cai | first = Jin-Yi | last2 = Sivakumar | first2 = D. | title = Sparse hard sets for P: resolution of a conjecture of Hartmanis | journal = Journal of Computer and System Sciences | volume = 58 | issue = 2 | pages = 280&ndash;296 | year = 1999 | doi = 10.1006/jcss.1998.1615 | url = http://citeseer.ist.psu.edu/501645.html| doi-access = free }}</ref>

'''P'''-complete problems may be solvable with different [[time complexity|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 ==
<references />

== References ==
* Greenlaw, Raymond, James Hoover, and Walter Ruzzo. 1995. ''Limits To Parallel computation; P-Completeness Theory''. {{isbn|0-19-508591-4}}. &mdash; Develops the theory, then catalogs 96 P-Complete problems.
* Satoru Miyano, Shuji Shiraishi, and Takayoshi Shoudai. ''A List of P-Complete Problems''. Kyushu University, [https://catalog.lib.kyushu-u.ac.jp/opac_download_md/3123/rifis-tr-17.pdf RIFIS-TR-CS-17]. December 1990.


{{ComplexityClasses}}

[[Category:Complexity classes]]