P
Definition
The polynomial time complexity class, denoted PTIME or P, is defined as follows. A language 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. The Church-Turing thesis states the notion of polynomial time is robust and does not change based on the nature of the machine, although 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).