LOGCFL

W teorii złożoności obliczeniowej LOGCFL jest klasą złożoności zawierającą wszystkie problemy decyzyjne , które można zredukować w przestrzeni logarytmicznej do języka bezkontekstowego . Ta klasa znajduje się pomiędzy NL a AC ¹ w tym sensie, że zawiera pierwszą i jest zawarta w drugiej. Problemy kompletne dla LOGCFL obejmują wiele problemów, których wystąpienia można scharakteryzować za pomocą hipergrafów acyklicznych :

• ocenianie acyklicznych boolowskich zapytań koniunkcyjnych
• sprawdzenie istnienia homomorfizmu między dwiema acyklicznymi strukturami relacyjnymi
• sprawdzanie istnienia rozwiązań acyklicznych problemów spełniania ograniczeń

Zobacz też

• Lista klas złożoności

Linki zewnętrzne

• Zoo złożoności : LOGCFL