NP

Remarks

Equivalent form with certificates: $L \in \mathrm{NP}$ exactly when there are a polynomial $p$ and a language $V \in$ P of pairs such that $$w \in L \iff \text{there is } c \in \Sigma^* \text{ with } \abs{c} \le p(\abs{w}) \text{ and } (w, c) \in V.$$ The string $c$ is a certificate for $w$, and a machine deciding $V$ is a verifier.

Example: the set of composite numbers, written in binary, is in NP. A certificate for $m$ is a factor $d$ with $1 < d < m$, which has at most as many digits as $m$. The verifier checks that $d$ divides $m$ by one division, in polynomial time.

Non-example: a certificate whose length grows like $2^{\abs{w}}$ is not allowed, because the definition bounds $\abs{c}$ by a polynomial in $\abs{w}$.

Every language in P is in NP, with the empty certificate, so $\mathrm{P} \subseteq \mathrm{NP}$. The name stands for "nondeterministic polynomial time".