P (complexity)

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"; 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.

...
Wikipedia