===Определение===
Определение класса NP через [[Класс NTIME/класс NTIME]] и [[Класс NSPACE|класс NSPACE]].
<tex>NP=\bigcup_{i=0}^{\infty} NTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} NTIME(in^k)</tex>
===NTIME===
Классом NTIME(f) по аналогии с [[Класс DTIME|DTIME]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и время ее работы не превосходит <tex>f(n)</tex>, где <tex>n</tex> - длина входа.
<tex>NTIME(f(n)) = \{ L | \exists НМТ m : L(m)=L, T(m,x) \le f(|x|) \}</tex>.
===NSPACE===
Классом NSPACE(f) по аналогии с [[Класс DSPACE|DSPACE]] называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входа.
<tex>NSPACE(f(n)) = \{ L \mid \exists НМТ m : L(m)=L, \delta (m,x) \le f(|x|) \}</tex>.
===Класс <tex>\Sigma_1</tex>===
