Configuration graph
Configuration graph is a theoritical tools used in Computational complexity theory to prove relation between Graph Reachability and complexity classes.
Introduction
Definition
A theorical computational models, like Turing machine or finite automata, explains how to do a computation, the models explains both what is an initial configuration of the machine and how to do steps to continue the computation, until we eventually stop. A configuration 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 letter, 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 accept if and only if there is a path from an initial vertex to an accepting vertex.
Usefull 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 intial vertex with an edge to every initial vertices, and a dummy accepting vertex with an edge from every accepting vertex then checking if there is an accepting computation only ask to go check if there is a path from one vertex to one other 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 is no restriction on the possible configuration; indeed it is easy to see that there are Turing Machine we can reach configuration of arbitrarily big size. But we can also have finite graph, 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 usefull because it reduces computational problems to graph reachability problems. For example, since reachability is in NL when we can represent configurations with a space logarithm in the size of the input, and since the configuration of the Turing Machin in NL is indeed of logarithm size, then graph-reachability is complete for NL[1].
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 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.
References
- ^ Papadimitriou, Christos H. (1994). Computational Complexity, Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1.
- Sanjeev Arora and Boaz Barak (2009). Computational complexity, a modern approach. ISBN 978-0-521-42426-4.
{{cite book}}: Text "publisher Cambridge University Press" ignored (help) Section 4.3: NL-completeness, p.87.