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}}$ ${\displaystyle 2^{n^{c}}}$

Eh

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 \exists y_{1}\forall y_{2}\dots 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})}$ ${\displaystyle 2^{c|x|}}$ ${\displaystyle 2^{cn}}$

EXPERIENCIA

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}}}}$ ${\displaystyle 2^{n^{c}}}$ ${\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 \exists y_{1}\forall y_{2}\dots 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}}}$ ${\displaystyle 2^{n^{c}}}$

Comparación

E ⊆ NE ⊆ EH⊆ ESPACIO ,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPESPACIO ,

EH ⊆ EXPH.

Referencias

1. Sarah Mocas, Separación de clases en la jerarquía de tiempo exponencial de clases en PH , Theoretical Computer Science 158 (1996), no. 1–2, págs. 221–231.
2. Anuj Dawar, Georg Gottlob, Lauri Hella, Capturando clases de complejidad relativizadas sin orden, Mathematical Logic Quarterly 44 (1998), no. 1, págs. 109-122.
3. Hemachandra, Lane A. (1989). "La jerarquía exponencial fuerte colapsa". Revista de Ciencias de la Computación y de Sistemas . 39 (3): 299–322. doi :10.1016/0022-0000(89)90025-1.

Enlaces externos

Zoológico de la complejidad : Clase EH