LOGCFL - LOGCFL

v teorie výpočetní složitosti, LOGCFL je třída složitosti který obsahuje vše rozhodovací problémy které lze snížit na logaritmický prostor do a bezkontextový jazyk. Tato třída se nachází mezi NL a AC¹, v tom smyslu, že obsahuje první a je obsažena v druhé. Problémy, které jsou kompletní pro LOGCFL zahrnuje mnoho problémů, jejichž instance lze charakterizovat acyklický hypergrafy:

• hodnocení acyklické Booleovské spojovací dotazy
• kontrola existence a homomorfismus mezi dvěma acyklickými relační struktury
• kontrola existence řešení acyklické problémy s uspokojením omezení

Viz také

• Seznam tříd složitosti

externí odkazy

• Složitost Zoo: LOGCFL