Классы EXP, NEXP. Полнота языков EXP и NEXP
Определение
Полная задача в классе EXP
Существует полная в EXP задача
Доказательство
Полной задачей в
является задача (binary deterministic bounded halt):(
задаётся двоичной записью, - детерминированная машина Тьюринга)Докажем, что
. Симулируем работу детерминированной машины . Для этого потребуется время порядка , но . Таким образом, общее время работы и . Докажем, что любая задача из сводится к . Пусть , допускающая язык , работает за время , где - полином. Рассмотрим - функция сведения. Чтобы выписать свой результат на ленту ей потребуется полиномиальное от число шагов, так как запись имеет константную длину, и запись числа имеет длину порядка в двоичной системе.Полная задача в классе NEXP
Существует полная в NEXP задача
Доказательство
Полной задачей в
является задача (binary nondeterministic bounded halt):(
задаётся двоичной записью, - недетерминированная машина Тьюринга)Доказательство того, что
- полная задача в , аналогично предыдушему доказательству. Заметим, что при симуляции работы , в случае недетерминированного выбора симулирующая машина тоже делает недетерминированный выбор. Сведение совпадает с сведением с предыдущем доказательством.