Изменения

: Пусть <tex>L \in \mathrm{\Sigma_1}</tex>. Тогда существуют <tex>R(x,y)</tex> и полином <tex>p</tex> из определения <tex>\mathrm{\Sigma_1}</tex>. Построим недетерминированную программу <tex>q(x)</tex>, разрешающую <tex>L</tex>.

: Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. # : Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.

<tex>\gets \quad(\mathrm{NP} \subset \mathrm{\Sigma_1})</tex>.