Teoría de la complejidad descriptiva

En complejidad de circuitos , se puede demostrar que la lógica de primer orden con predicados arbitrarios es igual a AC ⁰ , la primera clase en la jerarquía AC . De hecho, existe una traducción natural de los símbolos de FO a nodos de circuitos, con${\displaystyle \forall ,\exists }$ser${\displaystyle \land }$y${\displaystyle \lor }$de tamaño n . La lógica de primer orden en una signatura con predicados aritméticos caracteriza la restricción de la familia AC ^{0 de circuitos a aquellos construibles en} tiempo logarítmico alterno . ^{[ 2 ]} La lógica de primer orden en una signatura con solo la relación de orden corresponde al conjunto de lenguajes libres de estrella . ^{[ 9 ] [ 10 ]}

La lógica de primer orden gana sustancialmente en poder expresivo cuando se amplía con un operador que calcula el cierre transitivo de una relación binaria. Se sabe que la lógica de cierre transitivo resultante caracteriza el espacio logarítmico no determinista (NL) en estructuras ordenadas. Immerman utilizó esto para demostrar que NL es cerrado bajo el complemento (es decir, que NL = co-NL). ^{[ 11 ]}

Al restringir el operador de cierre transitivo al cierre transitivo determinista , la lógica resultante caracteriza exactamente el espacio logarítmico en estructuras ordenadas.

En estructuras que tienen una función sucesora, NL también puede caracterizarse mediante fórmulas de Krom de segundo orden .

SO-Krom es el conjunto de consultas booleanas definibles mediante fórmulas de segundo orden en forma normal conjuntiva, de modo que los cuantificadores de primer orden son universales y la parte de la fórmula sin cuantificadores está en forma de Krom. Esto significa que la fórmula de primer orden es una conjunción de disyunciones, y en cada "disyunción" hay como máximo dos variables. Toda fórmula de Krom de segundo orden es equivalente a una fórmula de Krom existencial de segundo orden.

SO-Krom caracteriza NL en estructuras con una función sucesora. ^{[ 12 ]}

FO[LFP] es la extensión de la lógica de primer orden mediante un operador de punto fijo mínimo, que expresa el punto fijo de una expresión monótona. Esto amplía la lógica de primer orden con la capacidad de expresar recursión. El teorema de Immerman-Vardi, demostrado independientemente por Immerman y Vardi , muestra que FO[LFP] caracteriza PTIME en estructuras ordenadas. ^{[ 13 ] [ 14 ]}

A partir de 2025, aún está por verse si existe una lógica natural que caracterice a PTIME en estructuras no ordenadas.

El teorema de Abiteboul-Vianu establece que FO[LFP]=FO[PFP] en ​​todas las estructuras si y solo si FO[LFP]=FO[PFP]; por lo tanto, si y solo si P=PSPACE. Este resultado se ha extendido a otros puntos fijos. ^{[ 7 ]}

En presencia de una función sucesora, PTIME también puede caracterizarse mediante fórmulas de Horn de segundo orden.

SO-Horn es el conjunto de consultas booleanas definibles con fórmulas SO en forma normal disyuntiva, de modo que los cuantificadores de primer orden son todos universales y la parte de la fórmula sin cuantificadores está en forma de Horn , lo que significa que es un gran AND de OR, y en cada "OR" todas las variables, excepto posiblemente una, se niegan.

Esta clase es igual a P en estructuras con una función sucesora. ^{[ 15 ]}

Esas fórmulas pueden transformarse en fórmulas prenexas en lógica de Horn existencial de segundo orden. ^{[ 12 ]}

La demostración de Ronald Fagin en 1974 de que la clase de complejidad NP se caracterizaba exactamente por aquellas clases de estructuras axiomatizables en la lógica existencial de segundo orden fue el punto de partida de la teoría descriptiva de la complejidad. ^{[ 5 ] [ 16 ]}

Dado que el complemento de una fórmula existencial es una fórmula universal, se deduce inmediatamente que co-NP se caracteriza por una lógica universal de segundo orden. ^{[ 5 ]}

SO, lógica de segundo orden sin restricciones, es igual a la jerarquía polinómica PH . Más precisamente, tenemos la siguiente generalización del teorema de Fagin: El conjunto de fórmulas en forma normal prenexa donde los cuantificadores existenciales y universales de segundo orden se alternan k veces caracterizan el k -ésimo nivel de la jerarquía polinómica. ^{[ 17 ]}

A diferencia de la mayoría de las demás caracterizaciones de clases de complejidad, el teorema de Fagin y su generalización no presuponen un orden total en las estructuras. Esto se debe a que la lógica existencial de segundo orden es suficientemente expresiva como para referirse a los posibles órdenes totales en una estructura utilizando variables de segundo orden. ^{[ 18 ]}

La clase de todos los problemas computables en el espacio polinomial, PSPACE , se puede caracterizar aumentando la lógica de primer orden con un operador de punto fijo parcial más expresivo.

La lógica de punto fijo parcial , FO[PFP], es la extensión de la lógica de primer orden con un operador de punto fijo parcial, que expresa el punto fijo de una fórmula si existe y devuelve 'falso' en caso contrario.

La lógica de punto fijo parcial caracteriza a PSPACE en estructuras ordenadas. ^{[ 19 ]}

La lógica de segundo orden puede extenderse mediante un operador de cierre transitivo del mismo modo que la lógica de primer orden, dando como resultado SO[TC]. El operador TC ahora también puede tomar variables de segundo orden como argumento. SO[TC] caracteriza PSPACE . Dado que el ordenamiento puede referenciarse en la lógica de segundo orden, esta caracterización no presupone estructuras ordenadas. ^{[ 20 ]}

Definimos variables de orden superior. Una variable de orden${\displaystyle i>1}$tiene una aridad${\displaystyle k}$y representa cualquier conjunto de${\displaystyle k}$- tuplas de elementos de orden${\displaystyle i-1}$Generalmente se escriben 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 primer orden donde se añade cuantificación sobre variables de orden superior; por lo tanto, utilizaremos los términos definidos en el artículo sobre lógica de orden superior sin volver a definirlos.

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

Utilizando la notación estándar de la tetración ,${\displaystyle \exp _{2}^{0}(x)=x}$y${\displaystyle \exp _{2}^{i+1}(x)=2^{\exp _{2}^{i}(x)}}$.${\displaystyle \exp _{2}^{i+1}(x)=2^{2^{2^{2^{\dots ^{2^{x}}}}}}}$con${\displaystyle i}$veces${\displaystyle 2}$

Cada fórmula de orden${\displaystyle i}$th es equivalente a una fórmula en forma normal prenexa, donde primero escribimos la cuantificación sobre la variable de${\displaystyle i}$orden y luego una fórmula de orden${\displaystyle i-1}$en forma normal.

HO es igual a la clase ELEMENTARY de funciones elementales. Para ser más precisos,${\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}$, que significa una torre de${\displaystyle (i-2)}$ 2s, terminando con${\displaystyle n^{c}}$, dónde${\displaystyle c}$es una constante. Un caso especial de esto es que${\displaystyle \exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Blue}{\mathsf {NP}}}}$, que es exactamente el teorema de Fagin . Usando máquinas oráculo en la jerarquía polinómica ,${\displaystyle {\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)})^{\Sigma _{j}^{\mathsf {P}}})}$