Complejidad descriptiva es un libro de lógica matemática y teoría de la complejidad computacional de Neil Immerman . Se trata de la teoría de la complejidad descriptiva , un área en la que se demuestra que la expresibilidad de las propiedades matemáticas utilizando diferentes tipos de lógica es equivalente a su computabilidad en diferentes tipos de modelos de computación limitados por recursos. Fue publicado en 1999 por Springer-Verlag en su serie de libros Graduate Texts in Computer Science.
Temas
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 antecedentes en 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 lenguajes formales , clases de complejidad limitadas por recursos y 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 se ocupa de las definiciones inductivas, los 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 límites de recursos para máquinas paralelas de acceso aleatorio y complejidad de circuitos . [1] [2] [3]
El capítulo seis presenta los juegos de Ehrenfeucht – Fraïssé , una herramienta clave para demostrar la inexpresibilidad 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 inexpresibilidad de ciertos lenguajes en lógica de segundo orden. [1] [2] [3]
El capítulo nueve se ocupa de la complementación de lenguajes y el operador de cierre transitivo , incluido el teorema de Immerman-Szelepcsényi de 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 se refiere a la uniformidad en la complejidad de los circuitos (la distinción entre la existencia de circuitos para resolver un problema y su constructibilidad algorítmica), y el capítulo doce se refiere al papel de ordenar y contar predicados en caracterizaciones lógicas de clases de complejidad. El capítulo trece utiliza el lema de conmutación para los límites inferiores, y el capítulo catorce se refiere a las aplicaciones a las bases de datos y la verificación de modelos . Un capítulo final describe los temas que aún necesitan investigación en esta área. [1] [2] [3]
Audiencia y recepción
El libro está dirigido principalmente como una referencia a los investigadores en esta área, [1] pero también podría usarse como base para un curso de posgrado, y viene equipado con ejercicios para este propósito. Aunque afirma ser autónomo, el crítico W. Klonowski escribe que sus lectores deben comprender tanto la complejidad clásica como los conceptos básicos de la lógica matemática. [2]
El revisor Anuj Dawar escribe que parte de la promesa inicial de la complejidad descriptiva se ha visto empañada por su incapacidad para aplicar herramientas lógicas a los problemas centrales de la teoría de la complejidad, y por la necesidad de agregar adiciones similares a la computación a los lenguajes lógicos con el fin de utilizar ellos para caracterizar la computación. Sin embargo, escribe, el libro es útil como una forma de presentar a los investigadores esta línea de investigación y una forma menos explorada de abordar la complejidad computacional. [4]
Referencias
- ^ a b c d e Lindell, Steven (diciembre de 2001), "Revisión de la complejidad descriptiva ", The Bulletin of Symbolic Logic , 7 (4): 525–527, doi : 10.2307 / 2687799 , JSTOR 2687799
- ^ a b c d e Klonowski, W. (2001), "Revisión de la complejidad descriptiva ", Dinámica discreta en la naturaleza y la sociedad , 6 : 57–62, doi : 10.1155 / S1026022601000061
- ^ a b c Schöning, Uwe , "Revisión de la complejidad descriptiva ", zbMATH , Zbl 0918.68031
- ^ Dawar, Anuj (2001), "Revisión de la complejidad descriptiva ", Revisiones matemáticas , MR 1732784