ELEMENTARY

En teoría de la complejidad computacional, la clase de complejidad ELEMENTARY de las funciones recursivas elementales es la unión de las clases

${\begin{aligned}\mathrm {ELEMENTARY} &=\mathrm {EXP} \cup \mathrm {2EXP} \cup \mathrm {3EXP} \cup \cdots \\&=\mathrm {DTIME} (2^{n})\cup \mathrm {DTIME} (2^{2^{n}})\cup \mathrm {DTIME} (2^{2^{2^{n}}})\cup \cdots \end{aligned}}$

El nombre fue acuñado por László Kalmár, en el contexto de funciones recursivas e indecidibilidad; a pesar de su nombre, la mayoría de problemas en esta clase distan mucho de ser elementales. Algunos problemas naturalmente recursivos quedan fuera de ELEMENTARY, por lo que pertenecen más bien a NONELEMENTARY. Más particularmente, hay problemas en las clases asociadas a la recursión primitiva y a la recursión primitiva múltiple que no están en ELEMENTARY.​ Sabemos que

LOWER-ELEMENTARY $\subsetneq$ EXPTIME $\subsetneq$ ELEMENTARY $\subsetneq$ PR $\subsetneq$MR $\subsetneq$ R

Mientras que ELEMENTARY contiene aplicaciones acotadas de exponenciación (por ejemplo, $O(2^{2^{n}})$), PR permite hiperoperadores (por ejemplo, tetración) los cuales no están contenidos en ELEMENTARY.

Definición

Las definiciones de funciones recursivas elementales son similares a las de las funciones recursivas primitivas, excepto que la recursión primitiva se reemplaza por sumas y productos acotados. Todas las funciones están definidas sobre los números naturales. Las reglas de construcción de funciones recursivas elementales, son:

1. Función cero. Devuelve cero: f(x) = 0.
2. Función sucesor: f(x) = x + 1. A menudo recibe el nombre S, como en S(x). Por aplicación repetida de la función sucesor, se puede tener la adición.
3. Funciones de proyección: estas son utilizadas para ignorar argumentos. Por ejemplo, f(a, b) = a es una función de proyección.
4. Función de sustracción: f(x, y) = x − y si y < x, o 0 si y ≥ x. Esta función suele definirse en otros formalismos usando condicionales e iteración.

A partir de estas funciones básicas, se puede construir otras funciones recursivas elementales.

1. Composición: aplicando valores de alguna función recursiva elemental como argumento a otra función recursiva elemental. En f(x₁, ..., x_n) = h(g₁(x₁, ..., x_n), ..., gm(x₁, ..., x_n)) la función f es recursiva elemental si h es recursiva elemental y cada g_i es recursiva elemental.
2. Suma acotada: $f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ es recursiva elemental si g es recursiva elemental.
3. Producto acotado: $f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ es recursiva elemental si g es recursiva elemental.

Funciones recursivas elementales inferiores

La clase LOWER-ELEMENTARY está basada en las funciones recursivas elementales inferiores las cuales siguen la definición anterior, excepto que no se usa el producto acotado. Es decir, una función recursiva elemental inferior se construye a partir de cero, sucesor, proyección, composición de otras funciones recursivas elementales inferiores, o la suma acotada de otra funciones recursivas elementales inferiores.

Si bien las funciones recursivas elementales tienen potencialmente crecimiento mayor a exponencial, las funciones recursivas elementales inferiores tienen crecimiento polinómico.

Base para ELEMENTARY

La clase de funciones elementales coincide con la clausura con respecto a la composición de las proyecciones y uno de los conjuntos de funciones siguientes: $\{n+1,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,n^{m}\}$, $\{n+m,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,2^{n}\}$, $\{n+m,n^{2},n\,{\bmod {\,}}m,2^{n}\}$, en donde $n\,{\stackrel {.}{-}}\,m=\max\{n-m,0\}$ es la función de sustracción definida anteriormente.​​

Caracterización descriptiva

En complejidad descriptiva, ELEMENTARY es igual a la clase de consultas de orden superior.​ Esto significa que cada lenguaje en la clase de complejidad ELEMENTARY puede ser escrito como fórmula de orden superior que es cierta solo para los elementos del lenguaje. Más precisamente,
$\mathrm {NTIME} (2^{2^{\cdots {2^{O(n)}}}})=\exists {}HO^{i}$,
donde $\cdots$ indica una torre de exponenciación y $\exists {}HO^{i}$ es la clase de consultas que comienzan con cuantificadores existenciales de orden i' seguidos de una fórmula de orden (i − 1).

Referencias

• Datos: Q5323278