LOGCF

Clase de complejidad computacional

En la teoría de la complejidad computacional , LOGCFL es la clase de complejidad que contiene todos los problemas de decisión que se pueden reducir en el espacio logarítmico a un lenguaje libre de contexto . ^[1] Esta clase está cerrada bajo complementación. ^[1] Está situada entre NL y AC 1 , en el sentido de que contiene al primero ^[1] y está contenido en el segundo. ^[2] Los problemas que son completos para LOGCFL incluyen muchos problemas que se pueden caracterizar por hipergrafos acíclicos :

• Evaluación de consultas conjuntivas booleanas acíclicas ^[3]
• Comprobación de la existencia de un homomorfismo entre dos estructuras relacionales acíclicas ^[4]
• Comprobación de la existencia de soluciones de problemas de satisfacción de restricciones acíclicas ^[3]

Véase también

• Lista de clases de complejidad

Referencias

1. Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002), The Complexity Theory Companion, Textos en informática teórica: una serie EATCS, Springer, pág. 280, doi :10.1007/978-3-662-04880-1, ISBN 9783662048801
2. Kapron, Bruce M., ed. (2023), Lógica, autómatas y complejidad computacional: las obras de Stephen A. Cook, ACM Books, Morgan & Claypool, pág. 124, ISBN 9798400707803
3. Gottlob, Georg; Leone, Nicola; Scarcello, Francesco (2001), "La complejidad de las consultas conjuntivas acíclicas", Journal of the ACM , 48 (3): 431–498, doi :10.1145/382780.382783
4. Vortmeier, Nils; Kokkinis, Ioannis (2021), "La complejidad dinámica de los homomorfismos de hipergrafos acíclicos", en Kowalik, Lukasz; Pilipczuk, Michal; Rzazewski, Pawel (eds.), Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Varsovia, Polonia, 23-25 ​​de junio de 2021, Documentos seleccionados revisados , Lecture Notes in Computer Science, vol. 12911, Springer, págs. 232–244, arXiv : 2107.06121 , doi :10.1007/978-3-030-86838-3_18, ISBN 978-3-030-86837-6

Enlaces externos

• Zoológico de la complejidad : LOGCFL