P

P is the set of decision problems that can be solved in worst-case polynomial time:

• If the input is of size n, the running time must be O(n^k).
• Note that k can depend on the problem class, but not the particular instance.

All the decision problems mentioned above are in P.