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