Teoría de la complejidad descriptiva

Rama de la lógica matemática

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 que las componen. 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 por enunciados de lógica de segundo orden . Esta conexión entre la complejidad y la lógica de las estructuras finitas permite transferir fácilmente los resultados 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 definirlas.

En concreto, cada sistema lógico produce un conjunto de consultas que se pueden expresar en él. Las consultas, cuando se limitan a estructuras finitas, corresponden a los problemas computacionales de la teoría de la complejidad tradicional.

El primer resultado importante de la complejidad descriptiva fue el teorema de Fagin , expuesto por Ronald Fagin en 1974. En él se establecía que NP es precisamente el conjunto de lenguajes expresables por sentencias de lógica existencial de segundo orden ; es decir, lógica de segundo orden que excluye la cuantificación universal sobre relaciones , funciones y subconjuntos . Muchas otras clases fueron caracterizadas posteriormente de esta manera.

El escenario

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 . Usualmente 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 grafo y los elementos de la estructura lógica representan sus vértices. La longitud de la entrada será medida por el tamaño de la respectiva estructura. Cualquiera que sea la estructura, podemos asumir que hay relaciones que pueden ser probadas, por ejemplo " es verdadero si y solo si hay una arista de x a y " (en caso de que la estructura sea un grafo), o " es verdadero si y solo si la n -ésima letra de la cadena es 1". Estas relaciones son los predicados para el sistema lógico de primer orden. También tenemos constantes, que son elementos especiales de la respectiva estructura, por ejemplo si queremos verificar la alcanzabilidad en un grafo, tendremos que elegir dos constantes s (inicio) y t (terminal). ${\displaystyle E(x,y)}$ ${\displaystyle P(n)}$

En la teoría de la complejidad descriptiva a menudo asumimos que existe un orden total sobre los elementos y que podemos comprobar la igualdad entre ellos. Esto nos permite considerar los elementos como números: el elemento x representa el número n si y solo 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 adición y la multiplicación por relaciones ternarias tales que es verdadero si y solo si y es verdadero si y solo si ). ${\displaystyle (n-1)}$ ${\displaystyle y<x}$ ${\displaystyle bit(x,k)}$ ${\displaystyle plus(x,y,z)}$ ${\displaystyle x+y=z}$ ${\displaystyle times(x,y,z)}$ ${\displaystyle x*y=z}$

Descripción general de las caracterizaciones de las clases de complejidad

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

• La lógica de primer orden define la clase AC 0 , los lenguajes reconocidos por circuitos de tamaño polinomial de profundidad limitada, que es igual 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 transitivos simétricos o deterministas produce L , problemas resolubles en el espacio logarítmico. ^[2]
• La lógica de primer orden con un operador de cierre transitivo produce NL , los problemas se pueden resolver en el espacio logarítmico no determinista. ^[3]
• La lógica de primer orden con un operador de punto mínimo fijo da P , los problemas son solucionables 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 polinomial PH . ^[3]
• La lógica de segundo orden con un cierre transitivo (conmutativo o no) produce PSPACE , los problemas resolubles en el espacio polinomial. ^[5]
• La lógica de segundo orden con un operador de punto fijo mínimo da EXPTIME , los problemas se pueden resolver en tiempo exponencial. ^[6]
• HO , la clase de complejidad definida por la lógica de orden superior , es igual a ELEMENTAL ^[7]

Tiempo subpolinomial

FO sin ningún operador

En la 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, siendo 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 ⁰ 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]} ${\displaystyle \forall ,\exists }$ ${\displaystyle \land }$ ${\displaystyle \lor }$

Lógica de cierre transitivo

La lógica de primer orden gana sustancialmente en poder expresivo cuando se la complementa 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. Esto fue utilizado por Immerman para demostrar que el NL es cerrado bajo complemento (es decir, que NL = co-NL). ^[10]

Al restringir el operador de cierre transitivo al 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, la NL también puede caracterizarse 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 de modo que los cuantificadores de primer orden sean universales y la parte de la fórmula que no tenga cuantificadores esté en forma de 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. Toda fórmula de Krom de segundo orden es equivalente a una fórmula de Krom de segundo orden existencial.

SO-Krom caracteriza la NL en estructuras con una función sucesora. ^[11]

Tiempo polinomial

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

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

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 a PTIME en estructuras ordenadas. ^{[12] [13]}

A partir de 2022, aún no se sabe si existe una lógica natural que caracterice al PTIME en estructuras desordenadas.

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. ^[14]

Fórmulas de Horn de segundo orden

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 libre de cuantificadores de la fórmula está en forma de Horn , lo que significa que es un gran AND de OR, y en cada "OR" se niegan todas las variables excepto posiblemente una.

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

Estas fórmulas pueden transformarse en fórmulas prenex en lógica de Horn existencial 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 estaba caracterizada exactamente por aquellas clases de estructuras axiomatizables en la lógica existencial de segundo orden fue el punto de partida de la teoría de la complejidad descriptiva. ^{[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 prenex 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 ordenamiento total de las estructuras, ya 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á de NP

El punto fijo parcial es PSPACE

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 hay uno y devuelve 'falso' en caso contrario.

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

El cierre transitivo es PSPACE

La lógica de segundo orden se puede extender mediante un operador de clausura transitiva 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 variables de segundo orden como argumento. 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 se pueden reconocer 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. Existe una relación entre los algoritmos de orden th y no deterministas cuyo tiempo está limitado por niveles de exponenciales. ^[21] ${\displaystyle i}$ ${\displaystyle 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 . Se suelen escribir 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 en las que añadimos cuantificación sobre las variables de orden superior; por tanto, utilizaremos los términos definidos en el artículo de FO sin definirlos de nuevo. ${\displaystyle i>1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 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. Por lo tanto, HO es el conjunto de fórmulas con alternancias de cuantificadores de orden , comenzando con , seguido 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}^{i}}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle \exists }$ ${\displaystyle i-1}$

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

Forma normal

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

Relación con las clases de complejidad

HO es igual a la clase ELEMENTARY 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 que , que es exactamente el teorema de Fagin . Usando máquinas oráculo en la jerarquía polinómica , ${\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}$ ${\displaystyle (i-2)}$ ${\displaystyle n^{c}}$ ${\displaystyle c}$ ${\displaystyle \exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Blue}{\mathsf {NP}}}}$ ${\displaystyle {\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)})^{\Sigma _{j}^{\mathsf {P}}})}$

Notas

1. Immerman 1999, pág. 86
2. 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.
3. Immerman 1999, pág. 242
4. 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.
5. Immerman 1999, pág. 243
6. Abiteboul, Serge; Vardi, Moshe Y.; Vianu, Victor (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.
7. Hella, Lauri; Turull-Torres, José María (2006). "Computación de consultas con lógicas de orden superior". Ciencias de la Computación Teórica . 355 (2). Essex, Reino Unido: Elsevier Science Publishers Ltd.: 197–214. doi : 10.1016/j.tcs.2006.01.009 . ISSN  0304-3975.
8. Robert., McNaughton (1971). Autómatas sin contador. MIT Press. ISBN 0-262-13076-9.OCLC 651199926  .
9. Immerman 1999, pág. 22
10. 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.
11. Immerman 1999, pág. 153-4
12. Immerman, Neil (1986). "Consultas relacionales computables en tiempo polinomial". Información y Control . 68 (1–3): 86–104. doi : 10.1016/s0019-9958(86)80029-8 .
13. Vardi, Moshe Y. (1982). "La complejidad de los lenguajes de consulta relacionales (Resumen ampliado)". Actas del decimocuarto simposio anual de la ACM sobre teoría de la computación - STOC '82 . Nueva York, NY, EE. UU.: ACM. pp. 137–146. CiteSeerX 10.1.1.331.6045 . doi :10.1145/800070.802186. ISBN .  978-0897910705.S2CID 7869248  .
14. Serge Abiteboul, Moshe Y. Vardi , Victor Vianu : Lógica de puntos fijos, 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
15. Grädel, Erich (13 de julio de 1992). "Captura de clases de complejidad mediante fragmentos de lógica de segundo orden". Ciencias de la Computación Teórica . 101 (1): 35–57. doi : 10.1016/0304-3975(92)90149-A . ISSN  0304-3975.
16. Immerman 1999, pág. 115
17. Immerman 1999, pág. 121
18. Immerman 1999, pág. 181
19. Abiteboul, S.; Vianu, V. (1989). "Extensiones de punto fijo de la lógica de primer orden y lenguajes similares a los de registro de datos". [1989] Actas. Cuarto Simposio Anual sobre Lógica en Ciencias de la Computación . IEEE Comput. Soc. Press. págs. 71–79. doi :10.1109/lics.1989.39160. ISBN 0-8186-1954-6.S2CID206437693  .​
20. Harel, D.; Peleg, D. (1984-01-01). "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.
21. Hella, Lauri; Turull-Torres, José María (2006). "Computación de consultas con lógicas de orden superior". Ciencias de la Computación 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. Springer. ISBN 0-387-98600-6.OCLC 901297152  .

Enlaces externos

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