NP

$L \in NP \iff$ существует НДМТ и полином $p$ такие, что

• $\forall \omega \in \mathbb{B}^*: (T(\omega) \leq p(|\omega|)) \wedge (M(\omega) = 1 \iff \omega \in L)$

Сертификат, определение через детерминированную МТ

$L \in NP \iff$ существует ДМТ и полиномы $p$ и $q$:

• $\forall~x,y: T(x, y) \leq p(|x|)$
• $\forall x \in L: \exists y~(|y| < q(|x|) ):~M(x, y) = 1$
• $\forall x \not\in L: \forall y~(|y| < q(|x|)):~M(x, y) = 0$

$y$ называется сертификатом