1632
правки
Изменения
м
=== Существует полная в ''EXP'' задача ===
=== Существует полная в ''NEXP'' задача ===
(<tex>t</tex> задаётся двоичной записью, <tex>m</tex> - недетерминированная машина Тьюринга) Доказательство того, что <tex>BH_{2,N}</tex> - полная задача в <tex>NEXP</tex>, аналогично предыдушему доказательству. Заметим, что при симуляции работы <tex>НМТ</tex>, в случае недетерминированного выбора симулирующая машина тоже делает недетерминированный выбор. Сведение совпадает с предыдущем предыдущим доказательством.
rollbackEdits.php mass rollback
== Полная задача в классе ''EXP'' ==
====Доказательство====
== Полная задача в классе ''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>
