Графы конфигурации — это теоретический инструмент, используемый в теории вычислительной сложности для доказательства связи между достижимостью графа и классами сложности . [ нужна ссылка ]
Теоретическая вычислительная модель, такая как машина Тьюринга или конечный автомат , объясняет, как выполнять вычисления. Модель объясняет как начальную конфигурацию машины, так и шаги, которые можно предпринять для продолжения вычислений, пока мы в конце концов не остановимся. Конфигурация , также называемая мгновенным описанием (ID) , представляет собой конечное представление машины в данный момент времени. Например, для конечного автомата и заданного ввода конфигурацией будет текущее состояние и количество прочитанных букв, для машины Тьюринга — состояние, содержимое ленты и положение головы. Граф конфигурации — это ориентированный помеченный граф .где метки вершин — возможные конфигурации моделей и где есть ребро из одной конфигурации в другую, если оно соответствует вычислительному шагу модели. [ нужна ссылка ]
Исходная и принимающая конфигурации машины являются специальными вершинами графа конфигураций. Вычисление принимается тогда и только тогда, когда существует путь от начальной вершины к принимающей вершине.
Если существует ровно одно начальное состояние, то вычисление является детерминированным тогда и только тогда, когда из любой конфигурации существует не более одного возможного шага, то есть тогда и только тогда, когда граф имеет исходную степень 1. [ нужна цитата ]
После добавления фиктивной начальной вершины с ребром в каждую начальную вершину и фиктивной принимающей вершины с ребром из каждой принимающей вершины проверка наличия принимающего вычисления требует только проверки наличия пути из начальной вершины в принимающую. вершина, которая является проблемой достижимости .
Вычисление называется однозначным, если существует не более одного пути из исходной вершины в принимающую вершину.