53
правки
Изменения
→Доказательство
(<tex>t</tex> задаётся двоичной записью, <tex>m</tex> - недетерминированная машина Тьюринга)
Доказательство того, что <tex>BH_{2,N}</tex> - полная задача в <tex>NEXP</tex>, аналогично предыдушему доказательству. Заметим, что при симуляции работы <tex>НМТ</tex>, в случае недетерминированного выбора симулирующая машина тоже делает недетерминированный выбор. Сведение совпадает с предыдущем доказательством.
