Grafo de configuración

Los grafos de configuración son una herramienta teórica utilizada en la teoría de la complejidad computacional para demostrar una relación entre la alcanzabilidad de un grafo y las clases de complejidad .

Un modelo computacional teórico, como una máquina de Turing o un autómata finito , explica cómo realizar un cálculo. El modelo explica tanto la configuración inicial de la máquina como los pasos necesarios para continuar el cálculo hasta su finalización. Una configuración , también llamada descripción instantánea ( DI ), es una representación finita de la máquina en un momento dado. Por ejemplo, para un autómata finito y una entrada dada, la configuración será el estado actual y el número de letras leídas; para una máquina de Turing, será el estado, el contenido de la cinta y la posición del cabezal. Un grafo de configuración es un grafo dirigido etiquetado donde la etiqueta de los vértices representa las posibles configuraciones del modelo y donde existe una arista que conecta una configuración con otra si corresponde a un paso computacional del modelo.

La configuración inicial y la de aceptación de la máquina son vértices especiales del grafo de configuración. El cálculo se realiza si y solo si existe un camino desde un vértice inicial hasta un vértice de aceptación.

Si existe exactamente un estado inicial, entonces un cálculo es determinista si y solo si desde cualquier configuración hay como máximo un paso posible, es decir, si y solo si el grafo tiene grado de salida 1.

Una vez que se agrega un vértice inicial ficticio con una arista a cada vértice inicial y un vértice de aceptación ficticio con una arista desde cada vértice de aceptación, verificar si hay un cálculo de aceptación solo requiere verificar si hay un camino desde el vértice inicial hasta el vértice de aceptación, que es el problema de alcanzabilidad .

Se dice que un cálculo es inequívoco si existe como máximo un camino desde un vértice inicial hasta un vértice de aceptación.

Un ciclo en el gráfico corresponde a un bucle infinito en el cálculo.

El grafo computacional puede tener un tamaño infinito si no existen restricciones en las configuraciones posibles; de hecho, es fácil ver que existen máquinas de Turing que pueden alcanzar configuraciones arbitrariamente grandes.

También es posible tener grafos finitos: en autómata finito determinista con${\displaystyle s}$estados, para una palabra de tamaño determinado${\displaystyle n}$La configuración se compone de la posición de la cabeza y el estado actual. Por lo tanto, el gráfico es de tamaño${\displaystyle (n+1)s}$y la parte accesible desde el estado inicial es de tamaño${\displaystyle n+1}$.

Esta noción resulta útil porque reduce los problemas computacionales a problemas de alcanzabilidad de grafos .

Por ejemplo, dado que la alcanzabilidad se da en NL cuando podemos representar configuraciones en un espacio que es logarítmico en el tamaño de la entrada, y dado que la configuración de una máquina de Turing en NL es de hecho de tamaño logarítmico, se deduce que la alcanzabilidad de grafos es completa para NL. ^{[ 1 ]}

En sentido contrario, ayuda a verificar la complejidad de un modelo computacional; el problema de decisión para un modelo (determinista) cuyas configuraciones ocupan un espacio logarítmico con respecto al tamaño de la entrada pertenece a ( L ) NL . Este es, por ejemplo, el caso de los autómatas finitos y los autómatas finitos con un contador.

• Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional: un enfoque moderno . Cambridge University Press . ISBN 978-0-521-42426-4.Sección 4.3: Completitud NL, pág.  87.