LOGCFL

En complejidad computacional, LOGCFL es la clase de complejidad que contiene todos los problemas de decisión que pueden ser reducidos en espacio logarítmico a un lenguaje libre de contexto. Esta clase se sitúa entre NL y AC1, en el sentido que contiene la primera y es contenida por la segunda. Los problemas completos para LOGCFL (en el mismo sentido que la clase NP-completo con respecto a NP) incluye muchos problemas cuyas instancias pueden ser caracterizadas mediante hipergrafos acíclicos.

Enlaces externos

• Complexity Zoo: LOGCFL

• Datos: Q448600