Polynomial Complexity Class

complexity-theory

Definition

Polynomial Complexity Class

The complexity class $\text{P}$ is the set of all decision problems that can be solved in polynomial time (w.r.t. to the instance size).

The complexity class $\text{P}$ contains all decision problems $\mathcal{P}$ for which there exists an algorithm $\Pi$ such that, for all instances $I$ of $\mathcal{P}$, $\Pi$ runs polynomial.