Jerarquía exponencial

En la teoría de la complejidad computacional , la jerarquía exponencial es una jerarquía de clases de complejidad que es un análogo temporal exponencial de la jerarquía polinómica . Como en otras partes de la teoría de la complejidad, "exponencial" se utiliza con dos significados diferentes (límites exponenciales lineales para una constante c y límites exponenciales completos ), lo que da lugar a dos versiones de la jerarquía exponencial. ^{[1] [2]} A esta jerarquía a veces también se la denomina jerarquía exponencial débil , para diferenciarla de la jerarquía exponencial fuerte . ^{[2] [3]}${\displaystyle 2^{cn}}$$Estilo de visualización 2nc$

La clase de complejidad EH es la unión de las clases para todos los k , donde (es decir, lenguajes computables en tiempo no determinista para alguna constante c con un oráculo ) y . También se define ${\displaystyle \Sigma _{k}^{\mathsf {E}}}$${\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}}$${\displaystyle 2^{cn}}$${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$ ${\displaystyle \Sigma _{0}^{\mathsf {E}}={\mathsf {E}}}$

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

Una definición equivalente es que un lenguaje L está en si y solo si puede escribirse en la forma ${\displaystyle \Sigma _{k}^{\mathsf {E}}}$

${\displaystyle x\in L\iff \existe y_{1}\para todo y_{2}\puntos Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

donde es un predicado computable en el tiempo (que limita implícitamente la longitud de y _i ). También de manera equivalente, EH es la clase de lenguajes computables en una máquina de Turing alternada en el tiempo para algún c con muchas alternancias constantemente. ${\displaystyle R(x,y_{1},\ldots ,y_{n})}$$Estilo de visualización 2^{c|x|}}$${\displaystyle 2^{cn}}$

EXPH es la unión de las clases , donde (lenguajes computables en tiempo no determinista para alguna constante c con un oráculo), , y nuevamente: ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$${\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}}$$Estilo de visualización 2nc$${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$${\displaystyle \Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}}$

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

Un lenguaje L está en si y sólo si puede escribirse como ${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$

${\displaystyle x\in L\iff \existe y_{1}\para todo y_{2}\puntos Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

donde es computable en el tiempo para algún c , lo que nuevamente limita implícitamente la longitud de y _i . De manera equivalente, EXPH es la clase de lenguajes computables en el tiempo en una máquina de Turing alternada con muchas alternancias constantemente. ${\displaystyle R(x,y_{1},\ldots ,y_{k})}$${\displaystyle 2^{|x|^{c}}}$$Estilo de visualización 2nc$

E ⊆ NE ⊆ EH⊆ ESPACIO ,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPESPACIO ,

EH ⊆ EXPH.

Zoológico de la complejidad : Clase EH