# P (complexity)

In

## Definition

A 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 circuits. A language *L* is in P if and only if there exists a polynomial-time uniform family of Boolean circuits , such that

- For all , takes
*n*bits as input and outputs 1 bit - For all
*x*in*L*, - For all
*x*not in*L*,

The circuit definition can be weakened to use only a 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

^{[1]}The related class of function problems is FP

Several natural problems are complete for P, including *st*-connectivity (or reachability) on alternating graphs.^{[2]} The article on P-complete problems lists further relevant problems in P.

## Relationships to other classes

A generalization of P is

^{[3]}

^{[4]}a negative answer would imply .

P is also known to be at least as large as

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

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.^{[5]}

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 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,

## 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

## Alternative characterizations

In

^{[7]}Immerman ascribes this result to Vardi

^{[8]}and to Immerman.

^{[9]}

It was published in 2001 that PTIME corresponds to (positive)

^{[10]}

P can also be defined as an algorithmic complexity class for problems that are not decision problems^{}[11] (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

Kozen^{[12]} states that Cobham and Edmonds are "generally credited with the invention of the notion of polynomial time," though Rabin also invented the notion independently and around the same time (Rabin's paper^{[13]} was in a 1967 proceedings of a 1966 conference, while Cobham's^{[14]} was in a 1965 proceedings of a 1964 conference and Edmonds's^{[15]} 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, H. C. Pocklington, in a 1910 paper,^{[16]}^{[17]} 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

**^**Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P",*Annals of Mathematics*160 (2004), no. 2, pp. 781–793.- ISBN 978-0-387-98600-5.
**^**ISBN 0-02-360692-4.**^**"complexity theory - Why is co-P = P".*Stack Overflow*. Archived from the original on 14 October 2020. Retrieved 2020-10-14.**.****.****.****.****. Revised version in***Information and Control*, 68 (1986), 86–104.**for the proof****.****.****^**Rabin, Michael O. (1967). "Mathematical theory of automata".*Mathematical Aspects of Computer Science. Proc. Sympos. Appl. Math., Vol. XIX*. Amer. Math. Soc. pp. 153–175.**^**Cobham, Alan (1965). "The intrinsic computational difficulty of functions".*Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.)*. pp. 24–30.**.**- Pocklington, H. C.(1910–1912). "The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity".
*Proc. Camb. Phil. Soc*.**16**: 1–5. **.**

**
**## References

- .
- Cobham, Alan (1965). "The intrinsic computational difficulty of functions".
*Proc. Logic, Methodology, and Philosophy of Science II 1964*. North Holland. - Rabin, Michael O. (1967). "Mathematical theory of automata".
*Mathematical Aspects of Computer Science. Proc. 1966 Sympos. Appl. Math., Vol. XIX*. Amer. Math. Soc. pp. 153–175. - ISBN 0-262-03293-7. Section 34.1: Polynomial time, pp. 971–979.
- .
- . Section 7.2: The Class P, pp. 256–263;.

## External links