In computational complexity theory, P, also known as PTIME or DTIME(n^O(1)), is a fundamental complexity class. It contains all decision problems that 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 that are "efficiently solvable" or "tractable". This is inexact: 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.

A language L is in P if and only if there exists a deterministic Turing machine M, such that

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 ${\displaystyle \{C_{n}:n\in \mathbb {N} \}}$, such that

The circuit definition can be weakened to use only a logspace uniform family without changing the complexity class.

P is known to contain many natural problems, including the decision versions of linear programming, and finding a maximum matching. In 2002, it was shown that the problem of determining if a number is prime is in P. The related class of function problems is FP.

Several natural problems are complete for P, including st-connectivity (or reachability) on alternating graphs. The article on P-complete problems lists further relevant problems in P.

A generalization of P is NP, which is the class of decision problems decidable by a non-deterministic Turing machine that runs in polynomial time. Equivalently, it is the class of decision problems where each "yes" instance has a polynomial size certificate, and certificates can be checked by a polynomial time deterministic Turing machine. The class of problems for which this is true for the "no" instances is called co-NP. P is trivially a subset of NP and of co-NP; most experts believe it is a proper subset, although this belief (the ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$ hypothesis) remains unproven. Another open problem is whether NP = co-NP; since P = co-P, a negative answer would imply ${\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}$.