Los gráficos de configuración son una herramienta teórica utilizada en la teoría de la complejidad computacional para probar una relación entre la accesibilidad del gráfico 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 tomar para continuar con 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 del cabezal. Un gráfico de configuración es un gráfico etiquetado dirigidodonde la etiqueta de los vértices son las posibles configuraciones de los modelos y donde hay un borde 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 hay 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 de cualquier configuración hay como máximo un paso posible, entonces si y solo si el gráfico es de grado 1. [ cita requerida ]
Una vez que se agregan un vértice inicial ficticio con un borde a cada vértice inicial y un vértice aceptante ficticio con un borde de cada vértice aceptante, 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 vértice, que es el problema de accesibilidad .
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 aceptante.