Nondeterministic Polynomial Complexity Class

complexity-theory

Definition

Nondeterministic Polynomial Complexity Class

The complexity class $\text{NP}$ is the set of all decision problems $\mathcal{P}$ for which there exists a polynomial balanced and polynomial decidable certificate relation for $\mathcal{P}$.