Los gráficos de configuración son una herramienta teórica utilizada en la teoría de la complejidad computacional para demostrar una relación entre la accesibilidad de los gráficos y las clases de complejidad . [ cita requerida ]
Un modelo computacional teórico, como la máquina de Turing o los autómatas finitos , explica cómo hacer un cálculo. El modelo explica tanto qué es una configuración inicial de la máquina como qué pasos se pueden dar para continuar el cálculo, hasta que finalmente nos detengamos. Una configuración , también llamada descripción instantánea ( ID ), 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 de la cabeza. Un grafo de configuración es un grafo etiquetado dirigido donde la etiqueta de los vértices son las posibles configuraciones de los modelos y donde hay una arista de una configuración a otra si corresponde a un paso computacional del modelo. [ cita requerida ]
Las configuraciones iniciales y de aceptación de la máquina son vértices especiales del gráfico de configuración. El cálculo acepta si y solo si existe una ruta 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 a partir de cualquier configuración hay como máximo un paso posible, es decir, si y solo si el gráfico es de grado de salida 1. [ cita requerida ]
Una vez que se agregan un vértice inicial ficticio con una arista en cada vértice inicial y un vértice de aceptación ficticio con una arista en cada vértice de aceptación, verificar si hay un cálculo de aceptación solo requiere verificar si hay una ruta 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 aceptador.
Un ciclo en el gráfico corresponde a un bucle infinito en el cálculo.
El gráfico computacional puede ser de tamaño infinito si no hay restricciones en las posibles configuraciones; de hecho, es fácil ver que hay máquinas de Turing que pueden alcanzar configuraciones arbitrariamente grandes.
También es posible tener grafos finitos: en el Autómata finito determinista con estados, para una palabra dada de tamaño la configuración está compuesta por la posición de la cabeza y el estado actual. Por lo que el grafo es de tamaño , y la parte accesible desde el estado inicial es de tamaño .
Esta noción es útil porque reduce los problemas computacionales a problemas de accesibilidad de gráficos .
Por ejemplo, dado que la alcanzabilidad es en NL cuando podemos representar configuraciones en el 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 la otra dirección, ayuda a verificar la complejidad de un modelo computacional; el problema de decisión para un modelo (determinista) cuyas configuraciones son de un espacio logarítmico en el tamaño de la entrada está en ( L ) NL . Este es por ejemplo el caso de autómatas finitos y autómatas finitos con un contador.
