ELEMENTARY

En teoria de la complexitat computacional, la classe de complexitat ELEMENTARY de les funcions recursivas elementals és l'unió de les classes

$\begin{array}{cc}\mathrm{E}\mathrm{L}\mathrm{E}\mathrm{M}\mathrm{E}\mathrm{N}\mathrm{T}\mathrm{A}\mathrm{R}\mathrm{Y}& =\mathrm{E}\mathrm{X}\mathrm{P}\cup \mathrm{2}\mathrm{E}\mathrm{X}\mathrm{P}\cup \mathrm{3}\mathrm{E}\mathrm{X}\mathrm{P}\cup \cdots \\ & =\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^n)\cup \mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^{2^n})\cup \mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^{2^{2^n}})\cup \cdots \end{array}$

El nom va ser falcat per László Kalmár, en el context de funcions recursivas i indecidibilidad; a pesar del seu nom, la majoria de problemes en esta classe disten molt de ser elementals. Alguns problemes naturalment recursivos queden fòra de ELEMENTARY, per lo que pertanyen més be a NONELEMENTARY. Més particularment, hi ha problemes en les classes associades a la recursión primitiva i a la recursión primitiva múltiple que no estan en ELEMENTARY. Sabem que

LOWER-ELEMENTARY $⊊$ EXPTIME $⊊$ ELEMENTARY $⊊$ PR $⊊$MR $⊊$ R

Mentres que ELEMENTARY conté aplicacions acotades d'exponenciación (per eixemple, $O(2^{2^n})$), PR permet hiperoperadores (per eixemple, tetración) els quals no estan continguts en ELEMENTARY.

Definició

Les definicions de funcions recursivas elementals són similars a les de les funcions recursivas primitives, excepto que la recursión primitiva es reemplaça per sumes i productes acotats. Totes les funcions estan definides sobre els número natural. Les regles de construcció de funcions recursivas elementals, són:

1. Funció zero. Torna zero: f(x) = 0.
2. Funció successor: f(x) = x + 1. A sovint rep el nom S, com en S(x). Per aplicació repetida de la funció successor, es pot tindre l'adició.
3. Funcions de proyecció: estes són utilisades per a ignorar arguments. Per eixemple, f(a, b) = a és una funció de proyecció.
4. Funció de substracció: f(x, i) = x − i si i < x, o 0 si i ≥ x. Esta funció sol definir-se en atres formalisme usant condicionals i iteración.

A partir d'estes funcions bàsiques, es pot construir atres funcions recursivas elementals.

1. Composició: aplicant valors d'alguna funció recursiva elemental com a argument a una atra funció recursiva elemental. En f(x₁, ..., x_n) = h(g₁(x₁, ..., x_n), ..., gm(x₁, ..., x_n)) la funció f és recursiva elemental si h és recursiva elemental i cada g_i és recursiva elemental.
2. Suma acotada: $f(m,x_1,\dots ,x_n)=\sum _{i=0}^{m}g(i,x_1,\dots ,x_n)$ és recursiva elemental si g és recursiva elemental.
3. Producte acotat: $f(m,x_1,\dots ,x_n)=\prod _{i=0}^{m}g(i,x_1,\dots ,x_n)$ és recursiva elemental si g és recursiva elemental.

Funcions recursivas elementals inferiors

La classe LOWER-ELEMENTARY està basada en les funcions recursivas elementals inferiors les quals seguixen la definició anterior, excepto que no s'usa el producte acotat. És dir, una funció recursiva elemental inferior es construïx a partir de zero, successor, proyecció, composició d'atres funcions recursivas elementals inferiors, o la suma acotada d'una atra funcions recursivas elementals inferiors.

Si be les funcions recursivas elementals tenen potencialment creiximent major a exponencial, les funcions recursivas elementals inferiors tenen creiximent polinòmic.