Изменения

===Определение===

Определение класса 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>

===Класс <tex>\Sigma_1</tex>===

Классом <tex>\Sigma_1</tex> называется класс языков (задач) L, таких что для каждого из них существует полиномиальный верификатор сертификата(утверждения) R, а также полином p, такие что слово l принадлежит языку L тогда и только тогда, когда существует сертификат (утверждение) y, длина которого не превосходит заданного полинома p, и сертификат удовлетворяет верификатору.