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 de tiempo exponencial de la jerarquía polinomial . Como en otras partes de la teoría de la complejidad, "exponencial" se utiliza en dos significados diferentes (límites exponenciales linealespara una constante c , y límites exponenciales completos), lo que lleva a dos versiones de la jerarquía exponencial. [1] [2]
EH
EH es la unión de las clases para todo k , donde(es decir, lenguajes computables en tiempo no deterministapara alguna constante c con a oráculo ). Uno también define
Una definición equivalente es que una lengua L está en si y solo si se puede escribir en la forma
dónde 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 alterna en el tiempopara algunos c con muchas alternancias constantemente.
EXPH
EXPH es la unión de las clases , dónde (lenguajes computables en tiempo no determinista para alguna constante c con a oráculo), y de nuevo:
Un idioma L está en si y solo si se puede escribir como
dónde es computable en el tiempo para algún c , 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.
Comparación
Referencias
- ^ Sarah Mocas, Clases de separación en la jerarquía de tiempo exponencial de las clases en PH , Informática teórica 158 (1996), no. 1-2, págs. 221-231.
- ^ Anuj Dawar, Georg Gottlob, Lauri Hella, Capturando clases de complejidad relativizada sin orden, Mathematical Logic Quarterly 44 (1998), no. 1, págs. 109-122.