Problema no elemental

En la teoría de la complejidad computacional , un problema no elemental ^{[ 1 ]} es un problema que no pertenece a la clase ELEMENTARY . Como clase, a veces se denota como NONELEMENTARY. Es decir, incluye todos los problemas de decisión que no tienen solución algorítmica con un tiempo acotado por una función recursiva elemental . Estas funciones no crecen más rápido que una torre de exponenciación de altura fija (por ejemplo,${\displaystyle O(2^{2^{n}})}$). No todas las funciones recursivas primitivas son elementales; por ejemplo, la tetración crece demasiado rápido para ser incluida en la clase elemental.

La jerarquía de problemas decidibles más allá de los elementales se suele presentar a lo largo de la jerarquía de rápido crecimiento . ^{[ 2 ]}

Sean las funciones de la jerarquía${\displaystyle F_{0},F_{1},\dots ,F_{\omega },F_{\omega +1},\dots }$. Para cada ordinal${\displaystyle \alpha }$, definimos la clase${\displaystyle {\mathcal {F}}_{\alpha }}$ser la clase de funciones computables en tiempo${\displaystyle F_{\alpha }^{(k)}(n)}$, para alguna constante positiva${\displaystyle k}$Aquí, la notación${\displaystyle F^{(k)}}$indica iteración de función : es la función obtenida al aplicar${\displaystyle F}$repetidamente,${\displaystyle k}$veces. Es decir,$${\displaystyle {\mathcal {F}}_{\alpha }:=\bigcup _{k=1}^{\infty }{\mathsf {FDTIME}}(F_{\alpha }^{(k)}(n))}$$Ahora, define${\displaystyle {\mathsf {F}}_{\alpha }}$ser la clase de complejidad${\displaystyle \bigcup _{\beta <\alpha ,p\in {\mathcal {F}}_{\beta }}{\mathsf {DTIME}}(F_{\alpha }(p(n)))}$.

Con la definición, tenemos

• ELEMENTAL: la clase de problemas decidibles en tiempo${\displaystyle f(n)}$, dónde${\displaystyle f(n)}$es una función de torre exponencial de altura fija. En otras palabras,${\displaystyle {\mathsf {ELEMENTARY}}={\mathsf {DTIME}}(n)\cup {\mathsf {DTIME}}(2^{n})\cup {\mathsf {DTIME}}(2^{2^{n}})\cup \cdots }$.
• TORRE:${\displaystyle f(n)={\;}^{p(n)}2}$, dónde${\displaystyle p(n)}$es una función de torre exponencial de altura fija, y el superíndice denota tetración . En otras palabras,${\displaystyle f(n)=F_{3}(p(n))}$. En otras palabras,${\displaystyle {\mathsf {TOWER}}={\mathsf {DTIME}}({}^{n}2)\cup {\mathsf {DTIME}}({}^{2^{n}}2)\cup {\mathsf {DTIME}}({}^{2^{2^{n}}}2)\cup \cdots }$. En otras palabras,${\displaystyle {\mathsf {TORRE}}:={\mathsf {F}}_{3}}$.
• Relaciones públicas:${\displaystyle f(n)}$es una función recursiva primitiva . En otras palabras,${\displaystyle {\mathsf {PR}}={\mathsf {DTIME}}(F_{1})\cup {\mathsf {DTIME}}(F_{2})\cup {\mathsf {DTIME}}(F_{3})\cup \cdots }$.
• ACK:${\displaystyle f(n)=A(n,n)=F_{\omega}(n)}$, dónde${\displaystyle A}$es la función de Ackermann . En otras palabras,${\displaystyle {\mathsf {ACK}}:={\mathsf {F}}_{\omega }}$

Según el teorema de jerarquía temporal , ELEMENTARY y PR no tienen problemas completos. Sin embargo, TOWER y ACK sí tienen problemas completos.

TORRE - Problemas completos:

• Equivalencia de expresiones sin asteriscos (SFEq) ^{[ 2 ]}
• Satisfacibilidad de la lógica monádica débil de segundo orden de un sucesor (WS1S) ^{[ 2 ]}
• Satisfacibilidad del fragmento estriado de lógica de primer orden de WVO Quine ^{[ 3 ]}
• β-convertibilidad de dos términos cerrados en el cálculo lambda simplemente tipado ^{[ 4 ] [ 5 ]}

ACK - problemas completos:

• alcanzabilidad en sistemas de adición vectorial (VAS). ^{[ 6 ] [ 7 ]}
• alcanzabilidad en el sistema de adición de vectores etiquetados con estados (VASS) ^{[ 8 ]}
• alcanzabilidad en redes de Petri . ^{[ 9 ] [ 7 ]}

Otros problemas no elementales pero decidibles:

• el problema de la equivalencia de expresiones regulares con complementación ^{[ 10 ]}
• la teoría monádica de segundo orden con dos sucesores (véase S2S ) ^{[ 11 ]}
• la teoría de primer orden de cualquier álgebra de términos en una signatura que contiene al menos un símbolo de función binaria ^{[ 12 ]}
• Problema de contención finita (PCF): Dados dos sistemas de valor añadido (SVA) con conjuntos alcanzables finitos${\displaystyle \operatorname {Alcance} (V_{1}),\operatorname {Alcance} (V_{2})}$, decidir si${\displaystyle \operatorname {Reach} (V_{1})\subset \operatorname {Reach} (V_{2})}$. Se desconoce su nivel preciso de complejidad. Nótese que decidir si el conjunto alcanzable es finito es EXPSPACE-completo. ^{[ 2 ]}
• Se sabe que los problemas de cobertura y terminación de ciertas clases de sistemas de transición bien estructurados son${\displaystyle {\mathsf {F}}_{\omega },{\mathsf {F}}_{\omega ^{\omega }},{\mathsf {F}}_{\omega ^{\omega ^{\omega }}},}$o${\displaystyle {\mathsf {F}}_{\epsilon _{0}}}$-completo. ^{[ 13 ]}

Se recopila una lista extensa en ^{[ 2 ] .}