View source for Configuration graph

{{more refs|date=May 2016}}
'''Configuration graphs''' are a theoretical tool used in [[Computational complexity theory|computational complexity theory]] to prove a relation between [[Graph (discrete mathematics)|graph]] [[Reachability|reachability]] and [[Computational complexity theory#Complexity classes|complexity classes]].{{fact|date=May 2016}}

==Definition==
A theoretical computational model, like [[Turing machine]] 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.{{fact|date=May 2016}}

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 there exists exactly one initial state, then a computation is deterministic if and only if from any configuration there is at most one possible step, so if and only if the graph is of out-degree 1.{{fact|date=May 2016}}

Once a dummy initial vertex with an edge to every initial vertex and a dummy accepting vertex with an edge from every accepting vertex are added, 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]] problem.

A computation is said to be unambiguous if there exists at most one path from an initial vertex to an accepting vertex.

A cycle in the graph corresponds to an infinite loop in the computation.

==Size of the graph==
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 [[Deterministic finite automaton]] with <math>s</math> states, for a given word of size <math>n</math> the configuration is composed of the position of the head and the current state. So the graph is of size <math>(n+1)s</math>, and the accessible part from the initial state is of size <math>n+1</math>.

==Use of this object==
This notion is useful because it reduces computational problems to graph [[Reachability|reachability]] problems.

For example, since [[Reachability|reachability]] is in [[NL (complexity)|NL]] when we can represent configurations in space which is logarithmic in the size of the input, and since the configuration of a Turing Machine in NL is indeed of logarithmic size, it follows that graph-reachability is [[Complete (complexity)|complete]] for NL.<ref name="papa">[[Biography:Christos Papadimitriou|Papadimitriou, Christos H.]] (1994). ''Computational Complexity'', Reading, Massachusetts: Addison-Wesley. {{ISBN|0-201-53082-1}}.</ref>

In the other direction, it helps to verify the complexity of a computation model; the decision problem for a (deterministic) model whose configurations are of space which is logarithmic in the size of the input is in ([[L (complexity)|L]]) [[NL (complexity)|NL]]. This is for example the case of finite automata and finite automata with one counter.

==References==
{{Reflist}}

==Bibliography==
* {{cite book| first1=Sanjeev | last1=Arora |  first2=Boaz | last2=Barak | year=2009 | title=Computational complexity, a modern approach | publisher={{wipe|Cambridge University Press}} | isbn=978-0-521-42426-4}} Section 4.3: NL-completeness, p.&nbsp;87.

{{DEFAULTSORT:Computational Complexity Theory}}
[[Category:Computational complexity theory]]
[[Category:Application-specific graphs]]

{{Sourceattribution|Configuration graph}}