Teoría de la complejidad descriptiva
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 polinomial, 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 que los resultados se transfieran fácilmente de un área a otra, facilitando nuevos métodos de prueba y brindando evidencia adicional de que las principales clases de complejidad son de alguna manera "naturales" y no están ligadas a las específicas.máquinas abstractas 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 , expuesto por Ronald Fagin en 1974. Este estableció que NP es precisamente el conjunto de lenguajes expresables por oraciones 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 se caracterizaron más tarde de esa manera.
Cuando usamos 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 hay relaciones que se pueden probar, por ejemplo, " es verdadero si y sólo si hay una arista de x a y " (en caso de que la estructura sea un gráfico), o " es verdadero si y sólo si"La ené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 estructura respectiva, por ejemplo, si queremos verificar la accesibilidad en un gráfico, Habrá que elegir dos constantes s (inicio) y t (terminal).
En la teoría descriptiva de la complejidad a menudo asumimos que existe un orden total sobre los elementos y que podemos verificar la igualdad entre los elementos. Esto nos permite considerar los elementos como números: el elemento x representa el número n 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 n es 1. (Podemos reemplazar la suma y la multiplicación por relaciones ternarias tal que es verdadero iff y es verdadero sii ).
Si nos restringimos a estructuras ordenadas con una relación de sucesor y predicados aritméticos básicos, obtenemos las siguientes caracterizaciones: