ELEMENTAL

En la teoría de la complejidad computacional , la clase de complejidad consiste en los problemas de decisión que se pueden resolver en un tiempo limitado por una función recursiva elemental . Las funciones elementales de crecimiento más rápido se obtienen iterando una función exponencial, como por ejemplo para un número limitado de iteraciones, ${\displaystyle {\mathsf {ELEMENTAL}}}$${\estilo de visualización 2^{n}}$${\estilo de visualización k}$$${\displaystyle \left.{\begin{matrix}2^{\scriptstyle 2^{\scriptstyle 2^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle n}}}}}}\end{matrix}}\right\}k.}$$

Así, es la unión de las clases ${\displaystyle {\mathsf {ELEMENTAL}}}$

${\displaystyle {\begin{aligned}{\mathsf {ELEMENTAL}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {TIEMPODT}}\left(2^{n}\right)\cup {\mathsf {TIEMPODT}}\left(2^{2^{n}}\right)\cup {\mathsf {TIEMPODT}}\left(2^{2^{2^{n}}}\right)\cup \cdots .\end{aligned}}}$

A veces se describe como tiempo exponencial iterado , ^[1] aunque este término se refiere más comúnmente al tiempo limitado por la función de tetración . ^[2]

Esta clase de complejidad se puede caracterizar por una cierta clase de "autómatas de pila iterados", autómatas de pila que pueden almacenar el estado completo de un autómata de pila iterado de orden inferior en cada celda de su pila. Estos autómatas pueden calcular todos los lenguajes en , y no pueden calcular lenguajes más allá de esta clase de complejidad. ^[3] El teorema de jerarquía temporal implica que no tiene problemas completos .${\displaystyle {\mathsf {ELEMENTAL}}}$${\displaystyle {\mathsf {ELEMENTAL}}}$

Toda función recursiva elemental puede calcularse en un límite de tiempo de esta forma y, por lo tanto, todo problema de decisión cuyo cálculo utiliza sólo funciones recursivas elementales pertenece a la clase de complejidad . ${\displaystyle {\mathsf {ELEMENTAL}}}$