LOGCFL

計算複雑性理論において、複雑性クラス LOGCFL とは、文脈自由言語に還元可能な対数領域で解ける決定問題の集合である。"logarithmic space context-free language" の略。

NLとAC1の間に位置する。すなわち、NL を包含し、AC1 に包含される。LOGCFL完全な問題としては、具体的な問題を非周期的ハイパーグラフで表せる問題が多く含まれる。例えば次のような問題である。
 非周期的な論理積型クエリの評価
 2つの非周期的関係構造の間に準同型写像が存在するかのチェック
 非周期的制約充足問題に解が存在するかのチェック

 外部リンク 
 Complexity Zoo entry

Category:計算複雑性理論
Category:数学に関する記事