El procedimiento de decisión para la aritmética de Presburger tiene una complejidad de tiempo [matemática] O (2 ^ {2 ^ n}) [/ matemática], que es superexponencial pero aún en la clase de complejidad “Recursiva elemental”
Los problemas que son decidibles pero no elementales (crecen más rápido que cualquier torre de exponentes fijos que terminan en n, aunque no necesariamente tan rápido como la tetración) incluyen:
- decidir si dos expresiones regulares representan el mismo lenguaje (si se les permite usar complementos)
- el problema de decisión sobre álgebras de términos: ¿una oración particular de primer orden tiene una asignación satisfactoria en un álgebra libre en una firma dada? Puede pensar en un álgebra libre como una especie de árbol de sintaxis: tiene símbolos y operadores, pero no tiene un “significado” que le permita equiparar dos oraciones de otra manera que no sea la identidad trivial.
Es paradójico que esto haga que el problema sea más difícil que, por ejemplo, SAT, que es la satisfacción sobre un álgebra no libre, pero ahí está. La razón intuitiva es que en lugar de simplemente sustituir uno de los dos valores en cada variable, debe sustituirlo en una expresión completa, que es un número mucho mayor de posibilidades (técnicamente infinito, pero no así en la práctica).
- ¿Qué pasaría si le preguntas a AI si sus algoritmos son autoconsistentes?
- Cómo clasificar videos de YouTube usando el algoritmo de puntuación de Wilson
- Cómo resolver este problema SPOJ
- ¿Cómo uso cualquier biblioteca en Java que implemente la selección de funciones del algoritmo RELEIFF?
- ¿Cómo se debe comenzar a aprender Algoritmos?
- El problema de decisión para la “lógica monádica de segundo orden sobre los árboles”. Si vemos XML como un árbol etiquetado, un DTD XML es más o menos equivalente a una oración en lógica monádica de segundo orden. “Segundo orden” significa que los cuantificadores están sobre conjuntos, no objetos individuales. Ver https://arxiv.org/pdf/cs/0606062…
