LOGCFL
Sign in to saveIn computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language. This class is closed under complementation. It is situated between NL and AC1, in the sense that it contains the former and is contained in the latter. Problems that are complete for LOGCFL include many problems that can be characterized by acyclic hypergraphs: evaluating acyclic Boolean conjunctive queries checking the existence of a homomorphism between two acyclic relational structures checking the existence of solutio
Article · 日本語
計算複雑性理論において、複雑性クラス LOGCFL とは、文脈自由言語に還元可能な対数領域で解ける決定問題の集合である。"logarithmic space context-free language" の略。 NLとの間に位置する。すなわち、NL を包含し、AC1 に包含される。LOGCFL完全な問題としては、具体的な問題を非周期的ハイパーグラフで表せる問題が多く含まれる。例えば次のような問題である。 * 非周期的な論理積型クエリの評価 * 2つの非周期的関係構造の間に準同型写像が存在するかのチェック * 非周期的制約充足問題に解が存在するかのチェック
Abstract from DBpedia / Wikipedia · CC BY-SA