View source for P (complexity)

{{short description|Class of problems solvable in polynomial time}}
In [[computational complexity theory]], '''P''', also known as '''PTIME''' or '''[[DTIME]]'''(''n''<sup>O(1)</sup>), is a fundamental [[complexity class]]. It contains all [[decision problem]]s that can be solved by a [[deterministic Turing machine]] using a [[polynomial]] amount of [[computation time]], or [[polynomial time]].

[[Cobham's thesis]] holds that P is the class of computational problems that are "efficiently solvable" or "[[tractable problem|tractable]]". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful [[rule of thumb]].

==Definition==
A [[Formal language|language]] ''L'' is in P if and only if there exists a deterministic Turing machine ''M'', such that

* ''M'' runs for polynomial time on all inputs
* For all ''x'' in ''L'', ''M'' outputs 1
* For all ''x'' not in ''L'', ''M'' outputs 0

P can also be viewed as a uniform family of [[Boolean circuit]]s. A language ''L'' is in P if and only if there exists a [[Circuit complexity#Polynomial-time uniform|polynomial-time uniform]] family of Boolean circuits <math>\{C_n:n \in \mathbb{N}\}</math>, such that

* For all <math>n \in \mathbb{N}</math>, <math>C_n</math> takes ''n'' bits as input and outputs 1 bit
* For all ''x'' in ''L'', <math>C_{|x|}(x)=1</math>
* For all ''x'' not in ''L'', <math>C_{|x|}(x)=0</math>

The circuit definition can be weakened to use only a [[Circuit complexity#Logspace uniform|logspace uniform]] family without changing the complexity class.

==Notable problems in P==
P is known to contain many natural problems, including the decision versions of [[linear programming]], and finding a [[maximum matching]]. In 2002, it was shown that the problem of determining if a number is [[prime number|prime]] is in P.<ref>Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "[http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf PRIMES is in P]", ''Annals of Mathematics'' 160 (2004), no. 2, pp. 781–793.</ref> The related class of [[function problem]]s is [[FP (complexity)|FP]].

Several natural problems are complete for P, including [[st-connectivity|''st''-connectivity]] (or [[reachability]]) on alternating graphs.<ref name="Immerman Reachability">{{cite book | last = Immerman | first = Neil | author-link = Neil Immerman | title = Descriptive Complexity |title-link= Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | isbn = 978-0-387-98600-5}}</ref> The article on [[P-complete|P-complete problems]] lists further relevant problems in P.

==Relationships to other classes==
[[Image:Complexity subsets pspace.svg|300px|thumb|right|A representation of the relation among complexity classes]]
[[File:Complexity-classes-polynomial.svg|thumb|Inclusions of complexity classes including [[P (complexity)|P]], [[NP (complexity)|NP]], [[co-NP]], [[BPP (complexity)|BPP]], [[P/poly]], [[PH (complexity)|PH]], and [[PSPACE]]]]
A generalization of P is [[NP (complexity)|NP]], which is the class of [[decision problem]]s decidable by a [[non-deterministic Turing machine]] that runs in [[polynomial time]]. Equivalently, it is the class of decision problems where each "yes" instance has a polynomial size certificate, and certificates can be checked by a polynomial time deterministic Turing machine. The class of problems for which this is true for the "no" instances is called [[co-NP]]. P is trivially a subset of NP and of co-NP; most experts believe it is a proper subset,<ref>
{{Cite book|last1=Johnsonbaugh|first1=Richard F.|author-link1=Richard Johnsonbaugh|last2=Schaefer|first2=Marcus|title= Algorithms|year=2004|publisher=Pearson Education|isbn=0-02-360692-4|page=458}}</ref> although this belief (the <math>\mathsf{P} \subsetneq \mathsf{NP}</math> hypothesis) [[P versus NP problem|remains unproven]]. Another open problem is whether NP&nbsp;=&nbsp;co-NP; since P = co-P,<ref>{{Cite web|title=complexity theory - Why is co-P = P|url=https://stackoverflow.com/questions/40405347/why-is-co-p-p|url-status=live|archive-url=https://archive.today/20201014205301/https://stackoverflow.com/questions/40405347/why-is-co-p-p/40425607|archive-date=14 October 2020|access-date=2020-10-14|website=Stack Overflow}}</ref> a negative answer would imply <math>\mathsf{P} \subsetneq \mathsf{NP}</math>.

P is also known to be at least as large as [[L (complexity)|L]], the class of problems decidable in a [[logarithm]]ic amount of [[Memory space (computational resource)|memory space]]. A decider using <math>O(\log n)</math> space cannot use more than <math>2^{O(\log n)} = n^{O(1)}</math> time, because this is the total number of possible configurations; thus, L is a subset of P.  Another important problem is whether L = P. We do know that P = AL, the set of problems solvable in logarithmic memory by [[alternating Turing machine]]s. P is also known to be no larger than [[PSPACE]], the class of problems decidable in polynomial space. Again, whether P = PSPACE is an open problem. To summarize:

:<math>\mathsf{L} \subseteq \mathsf{AL} = \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME}.</math>

Here, [[EXPTIME]] is the class of problems solvable in exponential time. Of all the classes shown above, only two strict containments are known:

* P is strictly contained in EXPTIME. Consequently, all EXPTIME-hard problems lie outside P, and at least one of the containments to the right of P above is strict (in fact, it is widely believed that all three are strict).
* L is strictly contained in PSPACE.

The most difficult problems in P are [[P-complete]] problems.

Another generalization of P is [[P/poly]], or Nonuniform Polynomial-Time. If a problem is in P/poly, then it can be solved in deterministic polynomial time provided that an [[advice (complexity)|advice string]] is given that depends only on the length of the input. Unlike for NP, however, the polynomial-time machine doesn't need to detect fraudulent advice strings; it is not a verifier. P/poly is a large class containing nearly all practical problems, including all of [[Bounded-error probabilistic polynomial|BPP]]. If it contains NP, then the [[polynomial hierarchy]] collapses to the second level. On the other hand, it also contains some impractical problems, including some [[undecidable problem]]s such as the unary version of any undecidable problem.

In 1999, [[Jin-Yi Cai]] and D. Sivakumar, building on work by [[Mitsunori Ogihara]], showed that if there exists a [[sparse language]] that is P-complete, then L = P.<ref>{{Cite journal|last1=Cai|first1=Jin-Yi|author-link1=Jin-Yi Cai|last2=Sivakumar|first2=D.|title=Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis|date=April 1999|journal=[[Journal of Computer and System Sciences]]|volume=58|issue=2|pages=280–296|doi=10.1006/jcss.1998.1615|doi-access=free}}</ref>

[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|P in relation to probabilistic complexity classes ([[ZPP (complexity)|ZPP]], [[RP (complexity)|RP]], co-RP, [[BPP (complexity)|BPP]], [[BQP]], [[PP (complexity)|PP]]), all within [[PSPACE]]. It is unknown if any of these containments are strict.]]

P is contained in [[BQP]]; it is unknown whether this containment is strict.

==Properties==
Polynomial-time algorithms are closed under composition. Intuitively, this says that if one writes a function that is polynomial-time assuming that function calls are constant-time, and if those called functions themselves require polynomial time, then the entire algorithm takes polynomial time. One consequence of this is that P is [[low (complexity)|low]] for itself. This is also one of the main reasons that P is considered to be a machine-independent class; any machine "feature", such as [[random access]], that can be simulated in polynomial time can simply be composed with the main polynomial-time algorithm to reduce it to a polynomial-time algorithm on a more basic machine.

Languages in P are also closed under reversal, [[Intersection (set theory)|intersection]], [[Union (set theory)|union]], [[concatenation]], [[Kleene closure]], inverse [[homomorphism]], and [[Complement (complexity)|complementation]].<ref>{{cite book|last=Hopcroft|first=John E.|title=Introduction to automata theory, languages, and computation|year=2001|publisher=Addison-Wesley|location=Boston|isbn=978-0201441246|pages=425–426|edition=2.|author2=Rajeev Motwani |author3=Jeffrey D. Ullman }}</ref>

==Pure existence proofs of polynomial-time algorithms==
Some problems are known to be solvable in polynomial time, but no concrete algorithm is known for solving them. For example, the [[Robertson–Seymour theorem]] guarantees that there is a finite list of [[forbidden minor]]s that characterizes (for example) the set of graphs that can be embedded on a torus; moreover, Robertson and Seymour showed that there is an O(''n''<sup>3</sup>) algorithm for determining whether a graph has a given graph as a minor. This yields a [[nonconstructive proof]] that there is a polynomial-time algorithm for determining if a given graph can be embedded on a torus, despite the fact that no concrete algorithm is known for this problem.

==Alternative characterizations==
In [[descriptive complexity]], P can be described as the problems expressible in [[FO(LFP)]], the [[first-order logic]] with a [[least fixed point]] operator added to it, on ordered structures.  In Immerman's 1999 textbook on descriptive complexity,<ref>{{cite book | last = Immerman | first = Neil | author-link = Neil Immerman | title = Descriptive Complexity|title-link= Descriptive Complexity | year = 1999 | publisher = Springer-Verlag | location = New York | isbn = 978-0-387-98600-5 | page = 66}}</ref> Immerman ascribes this result to Vardi<ref>{{cite conference | last = Vardi | first = Moshe Y. | title = The Complexity of Relational Query Languages | book-title = STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing | year = 1982 | pages = 137–146 | doi = 10.1145/800070.802186}}</ref> and to Immerman.<ref>{{cite conference | last = Immerman | first = Neil | title = Relational Queries Computable in Polynomial Time | book-title = STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing | year = 1982 | pages = 147–152 | doi = 10.1145/800070.802187}}  Revised version in ''Information and Control'', 68 (1986), 86–104.</ref>

It was published in 2001 that PTIME corresponds to (positive) [[range concatenation grammars]].<ref name="Kallmeyer2010">{{cite book|author=Laura Kallmeyer|title=Parsing Beyond Context-Free Grammars|year=2010|publisher=Springer Science & Business Media|isbn=978-3-642-14846-0|pages=5 and 37}} citing http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf for the proof</ref>

P can also be defined as an algorithmic complexity class for problems that are not decision problems<ref name="Wegener2005">{{cite book|last = Wegener| first=Ingo|author-link=Ingo Wegener|title=Complexity Theory|year=2005|publisher=Springer-Verlag|isbn=978-3-540-21045-0|doi= 10.1007/3-540-27477-4|page=35}}</ref> (even though, for example, finding the solution to a [[2-satisfiability]] instance in polynomial time automatically gives a polynomial algorithm for the corresponding decision problem). In that case P is not a subset of NP, but P∩DEC is, where DEC is the class of decision problems.

==History==
[[Dexter Kozen|Kozen]]<ref>{{cite book | last = Kozen | first = Dexter C. | year = 2006 | title = Theory of Computation | publisher = Springer | isbn = 978-1-84628-297-3 | page = 4}}</ref> states that [[Alan Cobham (mathematician)|Cobham]] and [[Jack Edmonds|Edmonds]] are "generally credited with the invention of the notion of polynomial time," though [[Michael O. Rabin|Rabin]] also invented the notion independently and around the same time (Rabin's paper{{sfn|Rabin|1967}} was in a 1967 proceedings of a 1966 conference, while Cobham's{{sfn|Cobham|1965}} was in a 1965 proceedings of a 1964 conference and Edmonds's{{sfn|Edmonds|1965}} was published in a journal in 1965, though Rabin makes no mention of either and was apparently unaware of them). Cobham invented the class as a robust way of characterizing efficient algorithms, leading to [[Cobham's thesis]].  However, [[Henry Cabourn Pocklington|H. C. Pocklington]], in a 1910 paper,<ref>{{cite journal | last = Pocklington | first = H. C. | author-link=H. C. Pocklington | year = 1910–1912 | title = The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity | journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]] | volume = 16 | pages = 1–5}}</ref><ref>{{Cite book | last=Gautschi | first=Walter | author-link=Walter Gautschi | title=Mathematics of computation, 1943–1993: a half-century of computational mathematics: Mathematics of Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia | year=1994 | publisher=American Mathematical Society | location=Providence, RI  | isbn=978-0-8218-0291-5 | pages=503–504}}</ref> analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that ran in (moderately) exponential time.

==Notes==
{{reflist}}

==References==
* {{cite journal
| last = Edmonds | first = Jack | author-link=Jack Edmonds
| year = 1965
| title = Paths, trees, and flowers
| journal = Canadian Journal of Mathematics
| volume = 17
| pages = 449–467
| doi = 10.4153/CJM-1965-045-4}}
* {{Cite book
| last=Cobham | first=Alan | author-link=Alan Cobham (mathematician)
| year = 1965
| chapter = The intrinsic computational difficulty of functions
| title = Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress
| publisher = North Holland
| place = Amsterdam
| editor-last1 = Bar-Hillel | editor-first1=Yehoshua | editor-link1=Yehoshua Bar-Hillel
| pages = 24–30}}
* {{cite conference
| last = Rabin | first = Michael O. | author-link = Michael O. Rabin
| title = Mathematical theory of automata
| book-title = Mathematical Aspects of Computer Science
| series = Proceedings of Symposia in Applied Mathematics
| volume = 19
| year = 1967
| pages = 153–175
| publisher = American Mathematical Society
| doi = 10.1090/psapm/019}}
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw–Hill, 2001. {{isbn|0-262-03293-7}}. Section 34.1: Polynomial time, pp.&nbsp;971&ndash;979.
* {{Cite book | last=Papadimitriou | first=Christos H. | author-link=Christos H. Papadimitriou | title=Computational complexity | year=1994 | publisher=Addison–Wesley | location=Reading, Mass.  | isbn=978-0-201-53082-7 }}
* {{Cite book | last=Sipser | first=Michael | author-link=Michael Sipser | title=Introduction to the Theory of Computation, 2nd Edition | year=2006 | publisher=Course Technology Inc | isbn=978-0-534-95097-2}} Section 7.2: The Class P, pp.&nbsp;256&ndash;263;.

==External links==
* {{CZoo|Class P|P#p}} 
* {{CZoo|Class P/poly|P#ppoly}}

{{ComplexityClasses}}

[[Category:Complexity classes]]