Классы EXP, NEXP. Полнота языков EXP и NEXP

Определение

[math]EXP = \bigcup^{\infty}_{i=0}DTIME(2^{n^{i}})[/math]

[math]NEXP = \bigcup^{\infty}_{i=0}NTIME(2^{n^{i}})[/math]

Полнота класса EXP

Существует полная в EXP задача

Доказательство

Полной задачей в [math]EXP[/math] является задача [math]BH_{2,D}[/math](binary deterministic bounded halt): [math]BH_{2,D} =\{ \lt m, x, t\gt \mid m(x) = 1, T(m,x) \le t \}[/math]

([math]t[/math] задаётся двоичной записью, [math]m[/math] - детерминированная машина Тьюринга)

Докажем, что [math]BH_{2,D} \in EXP[/math]. Симулируем работу детерминированной машины [math]m[/math]. Для этого потребуется время порядка [math]t^{2}[/math], но [math]t \le 2^{|t|} \le 2^{|\lt m,x,t\gt |}[/math]. Таким образом, общее время работы [math]T \le (2^{|\lt m,x,t\gt |})^{2} = 2^{2n}[/math] и [math]BH_{2,D} \in EXP[/math]. Докажем, что любая задача из [math]EXP[/math] сводится к [math]BH_{2,D}[/math]. Пусть [math]L \in EXP, MT\enskip m[/math], допускающая язык [math]L[/math], работает за время [math]T \le 2^{p(n)}[/math], где [math]p(n)[/math] - полином. Рассмотрим [math]f : x \rightarrow \lt m,x,2^{p(n)}\gt [/math] - функция сведения. Чтобы выписать свой результат на ленту ей потребуется полиномиальное от [math]n[/math] число шагов, так как запись [math]m[/math] имеет константную длину, [math]|x| = n[/math] и запись числа [math]2^{p(n)}[/math] имеет длину порядка [math]p(n)[/math] в двоичной системе.

Полнота класса NEXP

Существует полная в NEXP задача

Доказательство

Полной задачей в [math]NEXP[/math] является задача [math]BH_{2,N}[/math](binary nondeterministic bounded halt): [math]BH_{2,N} =\{ \lt m, x, t\gt \mid m(x) = 1, T(m,x) \le t \}[/math]

([math]t[/math] задаётся двоичной записью, [math]m[/math] - недетерминированная машина Тьюринга)

Доказательство того, что [math]BH_{2,N}[/math] - полная задача в [math]NEXP[/math], аналогично предыдушему доказательству. Заметим, что при симуляции работы [math]НМТ[/math], в случае недетерминированного выбора симулирующая машина тоже делает недетерминированный выбор. Сведение совпадает с сведением с предыдущем доказательством.