P (complexity)

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

Cobham's thesis holds that P is the class of computational problems which are "efficiently solvable" or "tractable"; in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.

Read more about P (complexity):  Definition, Notable Problems in P, Relationships To Other Classes, Properties, Pure Existence Proofs of Polynomial-time Algorithms, Alternative Characterizations, History