График конфигурации - Configuration graph

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[papa-1] Пападимитриу, Христос Х. (1994). Вычислительная сложность, Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 0-201-53082-1.

[1]