HO (complejidad)

---

En complejidad descriptiva , una rama de la complejidad computacional , HO es la clase de complejidad de estructuras que pueden ser reconocidas por fórmulas de lógica de orden superior . La lógica de orden superior es una extensión de la lógica de primer orden y la lógica de segundo orden con cuantificadores de orden superior. La clase HO es igual a la clase de complejidad de tiempo ELEMENTAL . ^[1] Existe una relación entre el orden de th y los algoritmos no deterministas cuyo tiempo está limitado por niveles de exponenciales.${\ Displaystyle i}$${\ Displaystyle i-1}$

Definimos la variable de orden superior, una variable de orden tiene una aridad y representar cualquier conjunto de - tuplas de elementos de orden . Suelen escribirse en mayúsculas y con un número natural como exponente para indicar el orden. La lógica de orden superior es el conjunto de fórmulas de FO donde agregamos cuantificación sobre variables de orden superior, por lo tanto, usaremos los términos definidos en el artículo de FO sin definirlos nuevamente.${\ Displaystyle i> 1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle i-1}$

HO es el conjunto de fórmulas donde el orden de las variables es como máximo . HO es el subconjunto de las fórmulas de la forma donde es un cuantificador, significa que es una tupla de variable de orden con la misma cuantificación. Por tanto, es el conjunto de fórmulas con alternancias de cuantificadores de orden th, comenzando por y , seguidas de una fórmula de orden .${\displaystyle ^{i}}$${\displaystyle i}$${\displaystyle _{j}^{i}}$${\displaystyle \phi =\exists {\overline {X_{1}^{i}}}\forall {\overline {X_{2}^{i}}}\dots Q{\overline {X_{j}^{i}}}\psi }$${\displaystyle Q}$${\displaystyle Q{\overline {X^{i}}}}$${\displaystyle {\overline {X^{i}}}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i}$${\displaystyle \exists }$${\displaystyle i-1}$

---