Configuration graph
Encyclopedia
Configuration graphs are a theoretical tool used in computational complexity theory
to prove a relation between graph
reachability
and complexity classes.
or finite automata, explains how to do a computation. The model explains both what is an initial configuration of the machine and which steps can be taken to continue the computation, until we eventually stop. A configuration, also called an Instantaneous Description(ID) is a finite representation of the machine at a given time. For example, for a finite automata and a given input, the configuration will be the current state and the number of read letters, for a Turing machine it will be the state, the content of the tape and the position of the head. A configuration graph is a directed labeled graph where the label of the vertices are the possible configurations of the models and where there is an edge from one configuration to another if it correspond to a computational step of the model.
The initial and accepting configuration(s) of the machine are special vertices of the configuration graph. The computation accepts if and only if there is a path from an initial vertex to an accepting vertex.
Once we add a dummy initial vertex with an edge to every initial vertex and a dummy accepting vertex with an edge from every accepting vertex, checking if there is an accepting computation only requires to check if there is a path from the initial vertex to the accepting vertex, which is the reachability
problem. A cycle in the graph means that there is a possible infinite loop in the computation.
The computational graph can be of infinite size if there are no restrictions on possible configurations; indeed, it is easy to see that there are turing machines which can reach arbitrarily large configurations. It is also possible to have finite graphs: on finite automata, the configuration is composed of the position of the head and the current state, so the configuration graph is of size
.
problems.
For example, since reachability
is in NL
when we can represent configurations in space which is logarithmic in the size of the input, and since the configuration of the Turing Machine in NL is indeed of logarithmic size, then graph-reachability is complete
for NL.
In the other direction, it helps to verify the complexity of a computation model; the decision problem for a (deterministic) model whose configuration are of space which is logarithmic in the size of the input is in (L
) NL
. This is for example the case of finite automata and finite automata with one counter.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
to prove a relation between graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
reachability
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
and complexity classes.
Definition
A theoretical computational model, like Turing machineTuring machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
or finite automata, explains how to do a computation. The model explains both what is an initial configuration of the machine and which steps can be taken to continue the computation, until we eventually stop. A configuration, also called an Instantaneous Description(ID) is a finite representation of the machine at a given time. For example, for a finite automata and a given input, the configuration will be the current state and the number of read letters, for a Turing machine it will be the state, the content of the tape and the position of the head. A configuration graph is a directed labeled graph where the label of the vertices are the possible configurations of the models and where there is an edge from one configuration to another if it correspond to a computational step of the model.
The initial and accepting configuration(s) of the machine are special vertices of the configuration graph. The computation accepts if and only if there is a path from an initial vertex to an accepting vertex.
Useful property
If the computation is deterministic then from any configuration there is at most one possible step, so the graph is of out-degree 1, and there is exactly one initial state.Once we add a dummy initial vertex with an edge to every initial vertex and a dummy accepting vertex with an edge from every accepting vertex, checking if there is an accepting computation only requires to check if there is a path from the initial vertex to the accepting vertex, which is the reachability
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
problem. A cycle in the graph means that there is a possible infinite loop in the computation.
The computational graph can be of infinite size if there are no restrictions on possible configurations; indeed, it is easy to see that there are turing machines which can reach arbitrarily large configurations. It is also possible to have finite graphs: on finite automata, the configuration is composed of the position of the head and the current state, so the configuration graph is of size
.Use of this object
This notion is useful because it reduces computational problems to graph reachabilityReachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
problems.
For example, since reachability
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
is in NL
NL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
when we can represent configurations in space which is logarithmic in the size of the input, and since the configuration of the Turing Machine in NL is indeed of logarithmic size, then graph-reachability is complete
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...
for NL.
In the other direction, it helps to verify the complexity of a computation model; the decision problem for a (deterministic) model whose configuration are of space which is logarithmic in the size of the input is in (L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
) NL
NL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
. This is for example the case of finite automata and finite automata with one counter.