21.3. P

Now that we know what a Turing Machine is, the complexity class P is easy to define.

P is the class of all formal languages that can be decided in polynomial time by a deterministic Turing machine.

Given Theorem 21.2, P is also exactly the class of all formal languages that can be decided by a RAM in polynomial time. Given the equivalence between formal languages and decision problems, we often simply say that

P is the class of all decision problems that can be solved in polynomial time

(without the specific reference to a deterministic Turing machine or RAM and without expressing decision problems as formal languages).