Изменения

<math>\Sigma_1 \in NP</math>

Построим программу, работающую за полином(из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в NP.

<math>NP \in \Sigma_1</math>

Пусть <tex> L \in NP </tex>. Тогда существует НМТ m, распознающая L. Построим сертификат y как последовательность недетерминированных выборов машины m, приводящих к допуску слова. Верификатором сертификата R выберем структуру, симулирующую НМТ, возвращающую 0 при ошибке выполнения или завершении работы в недопускающем состоянии, и 1, если работа НМТ завершилась корректно в допускающем состоянии. Таким образом, <tex> L \in \Sigma_1 </tex>, что и требовалось доказать.