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

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

ЭХ

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

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

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

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

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

ЭКСФ

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

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

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

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

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

Сравнение

Е ⊆ NE ⊆ EH⊆ ESPACE ,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE ,

ЭХ ⊆ ЭКСФ.

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

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