83
правки
Изменения
м
Нет описания правки
Построим программу, работающую за полином(из свойств машины Тьюринга, возможно построить аналогичную машину Тьюринга, работающюю за полиномиальное время, возможно большее), которая будет проверять решение задачи, входящей в класс <tex>\Sigma_1</tex>. Таким образом покажем вхождение класса <tex>\Sigma_1 </tex> в NP.
<code>
m(x)
{
return R(x,y);
}
</code>
Вхождение доказано.
