График конфигурации

Графы конфигурации — это теоретический инструмент, используемый в теории сложности вычислений для доказательства связи между графа достижимостью и классами сложности .

Определение

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

Исходная и принимающая конфигурации машины являются особыми вершинами графа конфигурации. Вычисление принимается тогда и только тогда, когда существует путь от начальной вершины до принимающей вершины.

Полезное свойство

Если существует ровно одно начальное состояние, то вычисление является детерминированным тогда и только тогда, когда из любой конфигурации существует не более одного возможного шага, то есть тогда и только тогда, когда граф имеет исходящую степень 1.

После добавления фиктивной начальной вершины с ребром к каждой начальной вершине и фиктивной принимающей вершины с ребром из каждой принимающей вершины для проверки наличия принимающего вычисления требуется только проверить, существует ли путь от начальной вершины к принимающей вершине. вершина, что является проблемой достижимости .

Вычисление называется однозначным, если существует не более одного пути от начальной вершины до принимающей вершины.

Цикл на графике соответствует бесконечному циклу вычислений.

Размер графика

Вычислительный граф может иметь бесконечный размер, если нет ограничений на возможные конфигурации; действительно, легко увидеть, что существуют машины Тьюринга, которые могут достигать сколь угодно больших конфигураций.

Также возможно иметь конечные графы: на детерминированном конечном автомате с $s$ утверждает, для данного слова размера $n$ конфигурация состоит из положения головы и текущего состояния. Таким образом, график имеет размер $(n+1)s$, а доступная часть из исходного состояния имеет размер $n+1$.

Использование этого объекта

Это понятие полезно, поскольку оно сводит вычислительные проблемы к проблемам достижимости графа .

Например, поскольку достижимость находится в NL , когда мы можем представлять конфигурации в пространстве, логарифмическом по размеру входных данных, и поскольку конфигурация машины Тьюринга в NL действительно имеет логарифмический размер, из этого следует, что достижимость по графу является полной для НЛ.

С другой стороны, это помогает проверить сложность вычислительной модели; проблема решения для (детерминированной) модели, конфигурации которой имеют пространство, логарифмическое по размеру входных данных, находится в ( L ) NL . Это, например, случай конечных автоматов и конечных автоматов с одним счетчиком.

Библиография

• Арора, Санджив ; Барак, Вооз (2009). Вычислительная сложность, современный подход . Издательство Кембриджского университета . ISBN  978-0-521-42426-4 . Раздел 4.3: NL-полнота, с. 87.