Polynomial Time (P)

Polynomial time (P): a language $L$ is said to be solvable in polynomial time if there exists a deterministic Turing Machine $M$ s.t.:

• $M$ accepts $L$
• $T_M(n)\in O(n^k)$ is eventually dominated by a polynomial function

We can define $P=\{\text{all problems in polynomial time}\}$.