Экспоненциальная иерархия - Exponential hierarchy

В теория сложности вычислений, то экспоненциальная иерархия это иерархия классы сложности, что является экспоненциальное время аналог полиномиальная иерархия. Как и везде в теории сложности, «экспонента» используется в двух разных значениях (линейные экспоненциальные границы ${\displaystyle 2^{cn}}$ для постоянного c, и полные экспоненциальные оценки ${\displaystyle 2^{n^{c}}}$), что приводит к двум версиям экспоненциальной иерархии.^[1][2]

EH

EH - объединение классов ${\displaystyle \Sigma _{k}^{\mathsf {E}}}$ для всех k, где ${\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}}$ (т.е. языки, вычислимые в недетерминированный время ${\displaystyle 2^{cn}}$ для некоторой постоянной c с ${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$ оракул ). Один также определяет

${\displaystyle \Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {E}}={\mathsf {E}}^{\Sigma _{k-1}^{\mathsf {P}}}.}$

Эквивалентное определение: язык L в ${\displaystyle \Sigma _{k}^{\mathsf {E}}}$ тогда и только тогда, когда это можно записать в виде

${\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

где ${\displaystyle R(x,y_{1},\ldots ,y_{n})}$ вычислимый во времени предикат ${\displaystyle 2^{c|x|}}$ (что неявно ограничивает длину y_я). Точно так же EH - это класс языков, вычислимых на переменная машина Тьюринга во время ${\displaystyle 2^{cn}}$ для некоторых c с постоянно множеством чередований.

EXPH

EXPH - это объединение классов ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$, где ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}}$ (языки, вычислимые за недетерминированное время ${\displaystyle 2^{n^{c}}}$ для некоторой постоянной c с ${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$ оракул), и снова:

${\displaystyle \Pi _{k}^{\mathsf {EXP}}={\mathsf {coNEXP}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {EXP}}={\mathsf {EXP}}^{\Sigma _{k-1}^{\mathsf {P}}}.}$

Язык L в ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$ тогда и только тогда, когда это можно записать как

${\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

где ${\displaystyle R(x,y_{1},\ldots ,y_{k})}$ вычислимо во времени ${\displaystyle 2^{|x|^{c}}}$ для некоторых c, что снова неявно ограничивает длину y_я. Эквивалентно EXPH - это класс языков, вычислимых во времени. ${\displaystyle 2^{n^{c}}}$ на переменной машине Тьюринга с постоянно множеством чередований.

Сравнение

E ⊆ NE ⊆ EH ⊆ ESPACE,

EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE,

EH ⊆ EXPH.

использованная литература

1. Сара Мокас, Отделение классов в иерархии экспоненциального времени от классов в PH, Теоретическая информатика 158 (1996), вып. 1–2, с. 221–231.
2. Анудж Давар, Георг Готтлоб, Лаури Хелла, Захват релятивизированных классов сложности без порядка, Mathematical Logic Quarterly 44 (1998), нет. 1. С. 109–122.

внешние ссылки

Зоопарк сложности: Класс EH