In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, LOGCFL is the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms ...
that contains all
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
s that can be reduced in
logarithmic space
In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space., Definition&n ...
to a
context-free language
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...
. This class is situated between
NL and
AC1, in the sense that it contains the former and is contained in the latter. Problems that are
complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies ...
for LOGCFL include many problems whose
instance
Instantiation or instance may refer to:
Philosophy
* A modern concept similar to ''participation'' in classical Platonism; see the Theory of Forms
* The instantiation principle, the idea that in order for a property to exist, it must be had by ...
s can be characterized by
acyclic hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) ...
s:
* evaluating acyclic
Boolean conjunctive queries
* checking the existence of a
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "sa ...
between two acyclic
relational structure
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.
Universal algebra studies structures that generalize the algebraic structures such as ...
s
* checking the existence of solutions of acyclic
constraint satisfaction problem
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constr ...
s
See also
*
List of complexity classes
This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics.
Many of these classes have a 'co' partner which consists of the complemen ...
External links
*
Complexity classes
{{comp-sci-theory-stub