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 usa con dos significados diferentes (límites exponenciales lineales para una constante c y límites exponenciales completos ), lo que lleva a dos versiones de la jerarquía exponencial. ^{[1] [2]} Esta jerarquía a veces también se conoce como 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 todo k , donde (es decir, lenguajes computables en tiempo no determinista para alguna constante c con un oráculo ) y . Uno también 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 se encuentra una lengua L si y sólo si se puede escribir 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 implícitamente limita la longitud de y _i ). También de manera equivalente, EH es la clase de lenguajes computables en una máquina de Turing alterna en el tiempo para algunos c con muchas alternancias constantemente. ${\displaystyle R(x,y_{1},\ldots ,y_{n})}$ ${\displaystyle 2^{c|x|}}$ ${\displaystyle 2^{cn}}$

exp.

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}}}.}$

Una lengua 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 algunos 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 alterna 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 ⊆ ESPACIO EXP ,

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, carril A. (1989). "La fuerte jerarquía exponencial se derrumba". Revista de Ciencias de la Computación y de Sistemas . 39 (3): 299–322.

enlaces externos

Zoológico de Complejidad : Clase EH