Изменения

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