Hispanopedia Wiki
Articulo de referencia

ELEMENTAL

En la teoría de la complejidad computacional , la clase de complejidad mi L mi METRO mi norte T A R Y {\displaystyle {\mathsf {ELEMENTAL}}} Consiste en problemas de decisión que...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la complejidad computacional , la clase de complejidadmiLmiMETROminorteTARY{\displaystyle {\mathsf {ELEMENTAL}}}Consiste en problemas de decisión que pueden resolverse en un tiempo limitado por una función recursiva elemental . De forma equivalente, son problemas que pueden resolverse en un tiempo limitado por una función exponencial iterada con un número limitado de iteraciones.

Cada función recursiva elemental puede calcularse en un límite de tiempo de esta forma, y ​​por lo tanto, cada problema de decisión cuyo cálculo utiliza únicamente funciones recursivas elementales pertenece a la clase de complejidadmiLmiMETROminorteTARY{\displaystyle {\mathsf {ELEMENTAL}}}.

El teorema de la jerarquía temporal implica quemiLmiMETROminorteTARY{\displaystyle {\mathsf {ELEMENTAL}}}no tiene problemas completos . Problemas fuera demiLmiMETROminorteTARY{\displaystyle {\mathsf {ELEMENTAL}}}son los problemas no elementales .

Definición

Las funciones recursivas elementales de crecimiento más rápido se obtienen iterando una función exponencial como2norte{\displaystyle 2^{n}}para un número acotadok{\displaystyle k}de iteraciones, 222⋅⋅⋅norte}k.{\displaystyle \left.{\begin{matrix}2^{\scriptstyle 2^{\scriptstyle 2^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle n}}}}}}\end{matrix}}\right\}k.}

De este modo,miLmiMETROminorteTARY{\displaystyle {\mathsf {ELEMENTAL}}}es la unión de las clases

miLmiMETROminorteTARY=⋃k∈nortek-miincógnitaPAG=DTIMETROmi(2norte)∪DTIMETROmi(22norte)∪DTIMETROmi(222norte)∪⋯.{\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 acotado por la función de tetración . [ 2 ]

Caracterizaciones

Autómatas de pila iterados

Esta clase de complejidad se puede caracterizar por una cierta clase de "autómatas de pila iterados", autómatas de pila descendente 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 cualquier lenguaje enmiLmiMETROminorteTARY{\displaystyle {\mathsf {ELEMENTAL}}}y no puede calcular lenguajes más allá de esta clase de complejidad. [ 3 ]

Lógica de orden superior

En la teoría de la complejidad descriptiva , ELEMENTARY es igual a la clase HO de lenguajes que pueden describirse mediante una fórmula de lógica de orden superior . Esto significa que cada lenguaje en la clase de complejidad ELEMENTARY corresponde a una fórmula de orden superior que es verdadera para, y solo para, los elementos del lenguaje. Más precisamente,norteTIMETROmi(22⋯2O(norte))=∃HOi{\displaystyle {\mathsf {NTIME}}\left(2^{2^{\cdots {2^{O(n)}}}}\right)=\exists {}{\mathsf {HO}}^{i}}, donde ⋯ indica una torre de i exponenciaciones y∃HOi{\displaystyle \exists {}{\mathsf {HO}}^{i}}es la clase de consultas que comienzan con cuantificadores existenciales de orden i y luego una fórmula de orden ( i  −  1) . [ 4 ]

Notas

  1. ↑ "ELEMENTARY" , Complexity Zoo , consultado el 31 de julio de 2025
  2. ↑ Friedman 1999 .
  3. ↑ Engelfriet 1991 .
  4. ↑ Hella & Turull-Torres 2006 .

Referencias