Editing P (complexity) (section)

==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. PSPACE is equivalent to NPSPACE by [[Savitch's theorem]]. Again, whether P = PSPACE is an open problem. To summarize:

:<math>\mathsf{L} \subseteq \mathsf{AL} = \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} = \mathsf{NPSPACE} \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.