P

Definition

The polynomial time complexity class, denoted PTIME or P, is defined as follows. A language $L$ is said to be in the polynomial time complexity class if it satisfies the following equivalent conditions:

No.	Shorthand	Definition
1	single tape Turing machine	there exists a 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 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.

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