P

Definition

Loose definition

The polynomial time complexity class, denoted PTIME or P, is a deterministic time complexity class defined loosely as follows. A language is said to be in the polynomial time complexity class if there is a polynomial time algorithm for determining whether a string is in the language. Here, the polynomial is an upper bound on the time taken, it is in terms of the length of the string, it is a worst case measure (i.e., worst case over all possible strings of the length), and we are interested in the asymptotic behavior for sufficiently large strings.

Formal definitions

No.	Shorthand	Definition
1	single tape Turing machine	there exists a (deterministic) Turing machine using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, and that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.
2	multiple tape Turing machine	there exists a (deterministic) Turing machine with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, and that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.
3	machine with log-time random access	there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, and the program accepts a string if and only if it is in the language and rejects it otherwise, and that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.

Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language.

Key features

Robustness based on complexity-theoretic Church-Turing thesis

The complexity-theoretic Church-Turing thesis states the notion of polynomial time is robust and does not change based on the nature of the machine, as long as we are dealing with deterministic machines, and we do not have access to random oracles or quantum computing.

However, the degree of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine). There may be an algorithm on one kind of machine that takes time $O(N\log N)$ but on another machine takes time $O(N^{2})$ where $N$ is the length of the string.

Independence of algorithm from length of the string

The Turing machine, or more generally the program or algorithm used to determine whether a string is in the language, is independent of the length of the string. (Internally, it may make cases based on the length of the string, but that's a different matter). A related complexity class where the algorithm can take polynomial-sized advice based on the length of the string is termed P/poly.

Asymptotic nature

The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.

Worst case rather than average case

Further information: Worst case versus average case

As for most complexity classes, the definition of polynomial time must take into account the worst case time taken among possible input strings, including both the strings that are in the language and the strings that are not in the language. We are not trying to compute the average time taken among all possible input strings. It is true that a polynomial time algorithm must be polynomial time on average as well, but the converse need not be true.

Relation with other complexity classes

Larger complexity classes

Complexity class	Meaning	Proof of containment	Reverse containment -- separation result or open problem	Intermediate complexity classes
RP (randomized polynomial time)	allows use of random bits. In polynomial time, the algorithm returns a Yes or Maybe with Yes indicating that the string is definitely in the language. Probability of saying Maybe if the string is in the language is bounded away from 1.	RP contains P	open problem -- both separation and collapse plausible	click here
co-RP	complement of a language in RP.	co-RP contains P	open problem -- both separation and collapse plausible	click here
ZPP (zero-error probabilistic polynomial time)	intersection of RP and co-RP			click here
BPP (bounded-error probabilistic polynomial time)	allows use of random bits, probability of errors both ways.	BPP contains P	open problem -- both separation and collapse plausible	click here
PP (probabilistic polynomial time)	error rates are allowed to come close to half.	PP contains P		click here
NP (nondeterministic polynomial time)	allows coming up magically with a string that helps provide "proof"	NP contains P	P equals NP conjecture. Separation is widely believed, i.e., it is believed that P is not equal to NP.	click here
co-NP	complement of a language in NP.	co-NP contains P	equivalent to P equals NP conjecture	click here
NP intersect co-NP	the language is both in NP and co-NP	NP intersect co-NP contains P	Unknown, separation plausible but unclear.	click here
Sigma2P				click here
Pi2P				click here
Delta2P				click here
PH (polynomial hierarchy)				click here
PSPACE (polynomial space)	algorithm that requires polynomial space to write on in addition to the read-only input.			click here
Quasipolynomial time (sometimes abbreviated QP, but that might be confused with quantum polynomial time)	time taken is exponential in a polynomial of the logarithm of the input length			click here
SUBEXP (subexponential time)				click here

Smaller complexity classes

Complexity class	Meaning	Proof of containment	Reverse containment -- separation result or open problem	Intermediate complexity classes
NL (nondeterministic logspace)	in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Can be used nondeterministically				click here
L (deterministic logspace)	in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used nondeterministically				click here

Properties

Property	Satisfied?	Proof	Statement with symbols
self-complementary complexity class	Yes	P is self-complementary	If $L\in P$, then the complement $L^{c}$, defined as the set of strings not in $L$, is also in $P$.
determined by almost everywhere	Yes	?	If $L_{1}\in P$, and $L_{2}$ is another language such that $L_{1}\setminus L_{2}$ and $L_{2}\setminus L_{1}$ are both finite sets of strings, then $L_{2}\in P$.