Teoría de la complejidad descriptiva - Descriptive complexity theory

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 expresable 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 proporcionando evidencia adicional de que las principales clases de complejidad son de alguna manera "naturales" y no están vinculadas a las máquinas abstractas específicas utilizadas. para definirlos.

En concreto, cada sistema lógico produce un conjunto de consultas que se pueden expresar 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 , mostrado por Ronald Fagin en 1974. 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, la mayoría de ellas por Neil Immerman :

• La lógica de primer orden define la clase FO , correspondiente a AC ⁰ , los lenguajes reconocidos por circuitos de tamaño polinomial de profundidad acotada, que es igual a los lenguajes reconocidos por una máquina de acceso aleatorio concurrente en tiempo constante.
• La lógica de primer orden con un operador de cierre transitivo conmutativo agregado produce SL , que es igual a L , problemas que se pueden resolver en el espacio logarítmico.
• 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.
• En presencia de orden lineal, la lógica de primer orden con un operador de punto mínimo fijo da P , los problemas que se pueden resolver en tiempo polinómico determinista.
• La lógica existencial de segundo orden produce NP .
• La lógica universal de segundo orden (excluyendo la cuantificación existencial de segundo orden) produce co-NP.
• La lógica de segundo orden corresponde a PH , como se mencionó anteriormente.
• La lógica de segundo orden con un cierre transitivo (conmutativo o no) produce PSPACE , los problemas que se pueden resolver en el espacio polinómico.
• 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.
• ${\ Displaystyle \ existe {\ color {Azul} {\ mathsf {HO}}} ^ {i}}$, la lógica con cuantificador existencial de orden i seguido de una fórmula de orden es igual a${\ Displaystyle i-1}$${\ displaystyle {\ color {Blue} {\ mathsf {NTIME}}} (\ exp _ {2} ^ {i-2} (n ^ {O (1)}))}$
• ${\ displaystyle {\ mathsf {HO}} _ {j} ^ {i} = {\ color {Blue} {\ mathsf {NTIME}}} (\ exp _ {2} ^ {i-2} (n ^ { O (1)})) ^ {\ Sigma _ {j} ^ {\ mathsf {P}}}}$
• HO es igual a ELEMENTARY

Ver también

• SO (complejidad)
• FO (complejidad)
• Espectro de una oración

Referencias

• Ronald Fagin , Espectros de primer orden generalizados y conjuntos reconocibles de tiempo polinómico . Complejidad de la Computación , ed. R. Karp, SIAM-AMS Proceedings 7, págs. 27–41. 1974.
• Fagin, Ronald (1993). "Teoría de modelos finitos - una perspectiva personal" . Informática Teórica . 116 : 3-31. doi : 10.1016 / 0304-3975 (93) 90218-i .
• Immerman, Neil (1983). "Idiomas que capturan clases de complejidad". Actas del Decimoquinto Simposio Anual de ACM sobre Teoría de la Computación - STOC '83 . págs. 347–354. doi : 10.1145 / 800061.808765 . ISBN 0897910990.
• Immerman, Neil (1999). Complejidad descriptiva . Nueva York: Springer-Verlag. págs. 113-119. ISBN 0-387-98600-6..

Otras lecturas

• Shawn Hedman, Un primer curso de lógica: una introducción a la teoría de modelos, la teoría de la prueba, la computabilidad y la complejidad , Oxford University Press, 2004, ISBN  0-19-852981-3 , sección 10.3 es una introducción adecuada para estudiantes universitarios
• Grädel, Erich; Kolaitis, Phokion G .; Libkin, Leonid; Maarten, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde; Weinstein, Scott (2007). Teoría de modelos finitos y sus aplicaciones . Textos en Informática Teórica. Una serie EATCS. Berlín: Springer-Verlag . ISBN 978-3-540-00428-8. Zbl  1133.03001 .

enlaces externos

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