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

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

EH [ править ]

EH - это объединение классов для всех k , где (т.е. языков, вычислимых за недетерминированное время для некоторой константы c с оракулом ). Один также определяет ${\ displaystyle \ Sigma _ {k} ^ {\ mathsf {E}}}$${\ Displaystyle \ Sigma _ {k} ^ {\ mathsf {E}} = {\ mathsf {NE}} ^ {\ Sigma _ {k-1} ^ {\ mathsf {P}}}}$${\ displaystyle 2 ^ {cn}}$${\ Displaystyle \ Sigma _ {к-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 х \ в L \ iff \ существует y_ {1} \ forall y_ {2} \ dots Qy_ {k} R (x, y_ {1}, \ ldots, y_ {k}),}$

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

EXPH [ править ]

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

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

Сравнение [ править ]

E ⊆ NE ⊆ EH ESPACE ,

EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE ,

EH ⊆ EXPH.

Ссылки [ править ]

Внешние ссылки [ править ]

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