1632
правки
Изменения
м
rollbackEdits.php mass rollback
Существует полная в ''NEXP'' задача
====Доказательство====
Полной задачей в <tex>NEXP</tex> является задача <tex>BH_{2,N}</tex>(binary nondeterministic bounded halt):
<tex>BH_{2,N} =\{ \langle m, x, t \rangle \mid m(x) = 1, T(m,x) \le t \}</tex>
Сведение совпадает с предыдущим доказательством.