Descriptive Complexity es un libro sobre lógica matemática y teoría de la complejidad computacional escrito por Neil Immerman . Trata sobre la teoría de la complejidad descriptiva , un área en la que se demuestra que la expresividad de las propiedades matemáticas mediante diferentes tipos de lógica es equivalente a su computabilidad en diferentes tipos de modelos de computación con recursos limitados. Fue publicado en 1999 por Springer-Verlag en su serie de libros Graduate Texts in Computer Science.
El libro tiene 15 capítulos, agrupados aproximadamente en cinco capítulos sobre lógica de primer orden , tres sobre lógica de segundo orden y siete capítulos independientes sobre temas avanzados. [1] [2]
Los dos primeros capítulos proporcionan material de referencia sobre lógica de primer orden (incluida la aritmética de primer orden , el predicado BIT y la noción de una consulta de primer orden) y teoría de la complejidad (incluidos los lenguajes formales , las clases de complejidad limitadas por recursos y los problemas completos ). El capítulo tres comienza la conexión entre lógica y complejidad, con una prueba de que los lenguajes reconocibles de primer orden pueden reconocerse en el espacio logarítmico y la construcción de lenguajes completos para el espacio logarítmico, el espacio logarítmico no determinista y el tiempo polinomial . El cuarto capítulo trata de definiciones inductivas, operadores de punto fijo y la caracterización del tiempo polinomial en términos de lógica de primer orden con el operador de punto fijo mínimo. La parte del libro sobre temas de primer orden termina con un capítulo sobre caracterizaciones lógicas de los límites de recursos para máquinas de acceso aleatorio paralelas y complejidad de circuitos . [1] [2] [3]
El capítulo seis presenta los juegos de Ehrenfeucht-Fraïssé , una herramienta clave para demostrar la inexpresabilidad lógica, y el capítulo siete presenta la lógica de segundo orden. Incluye el teorema de Fagin que caracteriza el tiempo polinomial no determinista en términos de lógica existencial de segundo orden, el teorema de Cook-Levin sobre la existencia de problemas NP-completos y extensiones de estos resultados a la jerarquía polinomial . El capítulo ocho utiliza juegos para demostrar la inexpresabilidad de ciertos lenguajes en lógica de segundo orden. [1] [2] [3]
El capítulo nueve trata de la complementación de lenguajes y del operador de clausura transitiva , incluyendo el teorema de Immerman-Szelepcsényi que sostiene que el espacio logarítmico no determinista está cerrado bajo complementación. El capítulo diez proporciona problemas completos y una caracterización lógica de segundo orden del espacio polinomial . El capítulo once trata de la uniformidad en la complejidad de circuitos (la distinción entre la existencia de circuitos para resolver un problema y su constructibilidad algorítmica), y el capítulo doce trata del papel de ordenar y contar predicados en las caracterizaciones lógicas de clases de complejidad. El capítulo trece utiliza el lema de conmutación para límites inferiores, y el capítulo catorce trata de aplicaciones a bases de datos y verificación de modelos . Un capítulo final describe temas que aún necesitan investigación en esta área. [1] [2] [3]
El libro está pensado principalmente como referencia para los investigadores en esta área [1] , pero también podría utilizarse como base para un curso de posgrado y viene equipado con ejercicios para este propósito. Aunque afirma ser un libro independiente, el crítico W. Klonowski escribe que sus lectores deben comprender ya tanto la complejidad clásica como los conceptos básicos de la lógica matemática [2] .
El crítico Anuj Dawar escribe que parte de la promesa inicial de la complejidad descriptiva se ha visto empañada por su incapacidad de hacer que las herramientas lógicas se apliquen a los problemas centrales de la teoría de la complejidad y por la necesidad de añadir elementos similares a los de la computación a los lenguajes lógicos para usarlos para caracterizar la computación. No obstante, escribe, el libro es útil como una forma de introducir a los investigadores en esta línea de investigación y en una forma menos explorada de abordar la complejidad computacional. [4]