Teoría descriptiva de la complejidad

La complejidad descriptiva es una rama de la teoría de la complejidad computacional y de la teoría de modelos finitos que caracteriza las clases de complejidad por el tipo de lógica necesaria para expresar los lenguajes en ellas. Por ejemplo, PH , la unión de todas las clases de complejidad en la jerarquía polinómica, es precisamente la clase de lenguajes expresables mediante enunciados de lógica de segundo orden . Esta conexión entre la complejidad y la lógica de las estructuras finitas permite que los resultados se transfieran fácilmente de un área a otra, facilitando nuevos métodos de prueba y proporcionando evidencia adicional de que las principales clases de complejidad son de alguna manera "naturales" y no están ligadas a las máquinas abstractas específicas utilizadas. para definirlos.

Específicamente, cada sistema lógico produce un conjunto de consultas expresables en él. Las consultas, cuando se restringen a estructuras finitas, corresponden a los problemas computacionales de la teoría de la complejidad tradicional.

El primer resultado principal de la complejidad descriptiva fue el teorema de Fagin , demostrado por Ronald Fagin en 1974. Estableció que la NP es precisamente el conjunto de lenguajes expresables mediante oraciones de lógica existencial de segundo orden ; es decir, lógica de segundo orden que excluye la cuantificación universal de relaciones , funciones y subconjuntos . Posteriormente, muchas otras clases se caracterizaron de esta manera.

El ajuste

Cuando utilizamos el formalismo lógico para describir un problema computacional, la entrada es una estructura finita y los elementos de esa estructura son el dominio del discurso . Por lo general, la entrada es una cadena (de bits o sobre un alfabeto) y los elementos de la estructura lógica representan posiciones de la cadena, o la entrada es un gráfico y los elementos de la estructura lógica representan sus vértices. La longitud de la entrada se medirá por el tamaño de la estructura respectiva. Cualquiera que sea la estructura, podemos suponer que existen relaciones que se pueden probar, por ejemplo " es verdadera si y sólo si hay una arista de $x$ a $y$ " (en el caso de que la estructura sea un gráfico), o " es verdadera si y sólo si la $enésima$ letra de la cadena es 1." Estas relaciones son los predicados del sistema lógico de primer orden. También tenemos constantes, que son elementos especiales de la estructura respectiva, por ejemplo si queremos comprobar la accesibilidad en un gráfico, tendremos que elegir dos constantes s (inicio) y t (terminal). $E(x,y)$ $P(n)$

En la teoría descriptiva de la complejidad a menudo asumimos que existe un orden total entre los elementos y que podemos verificar la igualdad entre ellos. Esto nos permite considerar los elementos como números: el elemento $x$ representa el número $n$ si y sólo si hay elementos $y$ con . Gracias a esto también podemos tener el predicado primitivo "bit", donde es verdadero si solo el $k$ ésimo bit de la expansión binaria de $x$ es 1. (Podemos reemplazar la suma y la multiplicación por relaciones ternarias tales que sea verdadera si y solo si y es verdadera si y sólo si ). $(n-1)$ $y<x$ $bit(x,k)$ $plus(x,y,z)$ $x+y=z$ $tiempos(x,y,z)$ $x*y=z$

Resumen de caracterizaciones de clases de complejidad.

Si nos limitamos a estructuras ordenadas con una relación sucesora y predicados aritméticos básicos, obtenemos las siguientes caracterizaciones:

La lógica de primer orden define la clase AC 0 , los lenguajes reconocidos por circuitos de tamaño polinómico de profundidad limitada, que equivale a los lenguajes reconocidos por una máquina de acceso aleatorio concurrente en tiempo constante. ^[1]
La lógica de primer orden aumentada con operadores de cierre transitivo simétricos o deterministas produce L , problemas que se pueden resolver en el espacio logarítmico. ^[2]
La lógica de primer orden con un operador de cierre transitivo produce NL , los problemas que se pueden resolver en un espacio logarítmico no determinista. ^[3]
La lógica de primer orden con un operador de punto mínimo fijo da P , los problemas que se pueden resolver en tiempo polinomial determinista. ^[3]
La lógica existencial de segundo orden produce NP . ^[3]
La lógica universal de segundo orden (excluyendo la cuantificación existencial de segundo orden) produce co-NP . ^[4]
La lógica de segundo orden corresponde a la jerarquía polinómica PH . ^[3]
La lógica de segundo orden con una clausura transitiva (conmutativa o no) produce PSPACE , los problemas que se pueden resolver en el espacio polinomial. ^[5]
La lógica de segundo orden con un operador de punto mínimo fijo da EXPTIME , los problemas que se pueden resolver en tiempo exponencial. ^[6]
HO , la clase de complejidad definida por la lógica de orden superior , es igual a ELEMENTARY ^[7]

Tiempo subpolinomial

FO sin operadores

En complejidad de circuitos , se puede demostrar que la lógica de primer orden con predicados arbitrarios es igual a AC 0 , 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 ser y de tamaño $n$ . La lógica de primer orden en una firma con predicados aritméticos caracteriza la restricción de la familia de circuitos AC ^{0 a aquellos construibles en}tiempo logarítmico alterno . ^[1] La lógica de primer orden en una firma con solo la relación de orden corresponde al conjunto de lenguajes sin estrellas . ^[8]^[9] $\forall,\existe$ $\tierra$ $\lo$

Lógica de cierre transitivo

La lógica de primer orden gana sustancialmente en poder expresivo cuando se aumenta 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 (NL) no determinista en estructuras ordenadas. Immerman utilizó esto para demostrar que NL está cerrado bajo complemento (es decir, que NL = co-NL). ^[10]

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

Fórmulas de Krom de segundo orden

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

SO-Krom es el conjunto de consultas booleanas definibles con fórmulas de segundo orden en forma normal conjuntiva tal que los cuantificadores de primer orden son universales y la parte libre de cuantificadores de la fórmula está en forma Krom, lo que 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. Cada 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 función sucesora. ^[11]

Tiempo polinomial

En estructuras ordenadas, la lógica de punto mínimo fijo de primer orden captura PTIME :

Lógica de punto mínimo fijo de primer orden

FO[LFP] es la extensión de la lógica de primer orden mediante un operador de punto mínimo fijo, que expresa el punto fijo de una expresión monótona. Esto aumenta la lógica de primer orden con la capacidad de expresar recursividad. El teorema de Immerman-Vardi, mostrado de forma independiente por Immerman y Vardi , muestra que FO[LFP] caracteriza a PTIME en estructuras ordenadas. ^[12]^[13]

A partir de 2022, todavía está abierto si existe una lógica natural que caracterice a PTIME en estructuras desordenadas.

El teorema de Abiteboul-Vianu establece que FO[LFP]=FO[PFP] en todas las estructuras si y sólo si FO[LFP]=FO[PFP]; por lo tanto si y sólo si P=PSPACIO. Este resultado se ha extendido a otros puntos fijos. ^[14]

Fórmulas de Horn de segundo orden

En presencia de una función sucesora, PTIME también se puede caracterizar 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 libre de cuantificadores de la fórmula está en forma de Horn , lo que significa que es un gran AND de O, y en cada "O" se niegan todas las variables excepto posiblemente una.

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

Esas fórmulas se pueden transformar en fórmulas prenexas en la lógica existencial de Horn de segundo orden. ^[11]

Tiempo polinomial no determinista

teorema de fagin

La prueba de Ronald Fagin de 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. ^[4]^[16]

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

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 otras caracterizaciones de clases de complejidad, el teorema de Fagin y su generalización no presuponen un ordenamiento total de las estructuras. Esto se debe a que la lógica existencial de segundo orden es en sí misma lo suficientemente expresiva como para referirse a los posibles órdenes totales de una estructura utilizando variables de segundo orden. ^[18]

Más allá del NP

El punto fijo parcial es PSPACE

La clase de todos los problemas computables en el espacio polinómico, 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 la hay y devuelve "falso" en caso contrario.

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

El cierre transitivo es PSPACE

La lógica de segundo orden puede ampliarse mediante un operador de cierre transitivo de la misma manera que la lógica de primer orden, lo que da como resultado SO[TC]. El operador TC ahora también puede tomar como argumento variables de segundo orden. SO[TC] caracteriza a PSPACE . Dado que se puede hacer referencia al ordenamiento en la lógica de segundo orden, esta caracterización no presupone estructuras ordenadas. ^[20]

Funciones elementales

La clase de complejidad temporal ELEMENTARY de funciones elementales se puede caracterizar por HO , la clase de complejidad de estructuras que pueden reconocerse mediante 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 de la lógica de segundo orden con cuantificadores de orden superior. Existe una relación entre los algoritmos de orden ésimo y los no deterministas cuyo tiempo está limitado por niveles de exponenciales. ^[21] $i$ $i-1$

Definición

Definimos variables de orden superior. Una variable de orden tiene una aridad y representa 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 primer orden donde agregamos cuantificación sobre variables de orden superior; por lo tanto, utilizaremos los términos definidos en el artículo de FO sin definirlos nuevamente. $i>1$ $k$ $k$ $i-1$

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

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

forma normal

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

Relación con las clases de complejidad.

HO es igual a la clase ELEMENTAL de funciones elementales. Para ser más precisos, es decir, una torre de 2, que termina en , donde es una constante. Un caso especial de esto es el que es exactamente el teorema de Fagin . Usando máquinas Oracle en la jerarquía polinomial , ${\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))$ $(i-2)$ $n^{c}$ $c$ $\exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Azul}{\mathsf {NP}}}$ ${\mathsf {HO}}_{j}^{i}={\color {Azul}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{ O(1)})^{\Sigma _{j}^{\mathsf {P}}})$

Notas

^ ab Immerman 1999, pág. 86
^ Grädel, Erich; Schalthöfer, Svenja (2019). Espacio logarítmico sin elección. Procedimientos internacionales de informática de Leibniz (LIPIcs). vol. 138. págs. 31:1–31:15. doi :10.4230/LIPICS.MFCS.2019.31. ISBN 9783959771177.
^ abcd Immerman 1999, pag. 242
^ a b C Fagin, Ron (1974). "Espectros generalizados de primer orden y conjuntos reconocibles en tiempo polinomial". En Karp, Richard (ed.). Complejidad de la Computación . págs. 43–73.
^ Immerman 1999, pag. 243
^ Abiteboul, Serge; Vardi, Moshe Y.; Vianu, Víctor (15 de enero de 1997). "Lógicas de punto fijo, máquinas relacionales y complejidad computacional". Revista de la ACM . 44 (1): 30–56. doi : 10.1145/256292.256295 . ISSN 0004-5411. S2CID 11338470.
^ Hola, Lauri; Turull-Torres, José María (2006). "Computación de consultas con lógica de orden superior". Informática Teórica . 355 (2). Essex, Reino Unido: Elsevier Science Publishers Ltd.: 197–214. doi : 10.1016/j.tcs.2006.01.009 . ISSN 0304-3975.
^ Robert., McNaughton (1971). Autómatas sin contador. Prensa del MIT. ISBN 0-262-13076-9. OCLC 651199926.
^ Immerman 1999, pag. 22
^ Immerman, Neil (1988). "El espacio no determinista está cerrado bajo complementación". Revista SIAM de Computación . 17 (5): 935–938. doi :10.1137/0217058. ISSN 0097-5397.
^ ab Immerman 1999, pág. 153-4
^ Immerman, Neil (1986). "Consultas relacionales computables en tiempo polinómico". Información y Control . 68 (1–3): 86–104. doi : 10.1016/s0019-9958(86)80029-8 .
^ Vardi, Moshe Y. (1982). "La complejidad de los lenguajes de consulta relacionales (resumen ampliado)". Actas del decimocuarto simposio anual de ACM sobre teoría de la informática - STOC '82 . STOC '82. Nueva York, NY, Estados Unidos: ACM. págs. 137-146. CiteSeerX 10.1.1.331.6045 . doi : 10.1145/800070.802186. ISBN 978-0897910705. S2CID 7869248.
^ Serge Abiteboul, Moshe Y. Vardi , Victor Vianu : Lógicas de punto fijo, máquinas relacionales y complejidad computacional Revista del archivo ACM, volumen 44, número 1 (enero de 1997), páginas: 30-56, ISSN 0004-5411
^ Grädel, Erich (13 de julio de 1992). "Capturar clases de complejidad mediante fragmentos de lógica de segundo orden". Informática Teórica . 101 (1): 35–57. doi : 10.1016/0304-3975(92)90149-A . ISSN 0304-3975.
^ Immerman 1999, pag. 115
^ Immerman 1999, pag. 121
^ Immerman 1999, pag. 181
^ Abiteboul, S.; Vianu, V. (1989). "Extensiones de Fixpoint de lógica de primer orden y lenguajes similares a registros de datos". [1989] Actas. Cuarto Simposio Anual sobre Lógica en Informática . Computación IEEE. Soc. Prensa. págs. 71–79. doi :10.1109/lics.1989.39160. ISBN 0-8186-1954-6. S2CID 206437693.
^ Harel, D.; Peleg, D. (1 de enero de 1984). "Sobre lógicas estáticas, lógicas dinámicas y clases de complejidad". Información y Control . 60 (1): 86-102. doi : 10.1016/S0019-9958(84)80023-6 . ISSN 0019-9958.
^ Hola, Lauri; Turull-Torres, José María (2006). "Computación de consultas con lógica de orden superior". Informática Teórica . 355 (2). Essex, Reino Unido: Elsevier Science Publishers Ltd.: 197–214. doi : 10.1016/j.tcs.2006.01.009 . ISSN 0304-3975.

Referencias

Immerman, Neil (1999). Complejidad descriptiva. Saltador. ISBN 0-387-98600-6. OCLC 901297152.

enlaces externos

Página de complejidad descriptiva de Neil Immerman, que incluye un diagrama