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

${\displaystyle {\begin{aligned}{\mathsf {ELEMENTARY}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {DTIME}}\left(2^{n}\right)\cup {\mathsf {DTIME}}\left(2^{2^{n}}\right)\cup {\mathsf {DTIME}}\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 {ELEMENTARY}}}$ ${\displaystyle {\mathsf {ELEMENTARY}}}$

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 {ELEMENTARY}}}$

Referencias

1. "ELEMENTARY", Complexity Zoo , consultado el 3 de noviembre de 2024
2. Friedman, Harvey (1999), "Algunos problemas de decisión de enorme complejidad" (PDF) , 14.º Simposio anual IEEE sobre lógica en informática, Trento, Italia, 2-5 de julio de 1999 , {IEEE} Computer Society, págs. 2-12, doi :10.1109/LICS.1999.782577, MR  1942515
3. Engelfriet, Joost (1991), "Autómatas de pila iterados y clases de complejidad", Información y computación , 95 (1): 21–75, doi :10.1016/0890-5401(91)90015-T, MR  1133778