ELEMENTARY

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda

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

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.[1]​ Sabemos que

LOWER-ELEMENTARY EXPTIME ELEMENTARY PR MR R

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

Definición[editar]

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) = xy 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(x1, ..., xn) = h(g1(x1, ..., xn), ..., gm(x1, ..., xn)) la función f es recursiva elemental si h es recursiva elemental y cada gi es recursiva elemental.
  2. Suma acotada: es recursiva elemental si g es recursiva elemental.
  3. Producto acotado: es recursiva elemental si g es recursiva elemental.

Funciones recursivas elementales inferiores[editar]

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[editar]

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: , , , en donde es la función de sustracción definida anteriormente.[2][3]

Caracterización descriptiva[editar]

En complejidad descriptiva, ELEMENTARY es igual a la clase de consultas de orden superior.[4]​ 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,
,
donde indica una torre de exponenciación y es la clase de consultas que comienzan con cuantificadores existenciales de orden i' seguidos de una fórmula de orden (i − 1).

Referencias[editar]

  1. Sylvain Schmitz. «COMPLEXITY HIERARCHIES BEYOND ELEMENTARY». 
  2. Mazzanti, S., "Plain Bases for Classes of Primitive Recursive Functions", Mathematical Logic Quarterly, 48 (2002) 93–104
  3. "Superpositions of elementary arithmetic functions", S. S. Marchenkov, Journal of Applied and Industrial Mathematics, September 2007, Volume 1, Issue 3, pp 351-360, doi 10.1134/S1990478907030106.
  4. Lauri Hella and José María Turull-Torres (2006), «Computing queries with higher-order logics», Theoretical Computer Science ((what is called "number" in bibtex) edición) (Essex, UK: Elsevier Science Publishers Ltd.) 355 (2): 197-214, ISSN 0304-3975, doi:10.1016/j.tcs.2006.01.009