st-подключение - st-connectivity

В информатике , ули связность или ЭСТЕКОН является проблема решения запрашиваемой для вершины s и т в ориентированном графе , если т является достижимым из с .

Формально проблема решения задается следующим образом:

PATH = {⟨ D ,  s ,  т ⟩ | D - ориентированный граф с путем от вершины s к t } .

Сложность

Можно показать, что проблема заключается в NL , поскольку недетерминированная машина Тьюринга может угадать следующий узел пути, в то время как единственная информация, которая должна быть сохранена, - это общая длина пути и какой узел в настоящее время рассматривается. Алгоритм завершается, если либо достигается целевой узел t , либо длина пути превышает n , количество узлов в графе.

Дополнение к st-связности , известное как st- несвязность, также принадлежит классу NL, поскольку NL = coNL по теореме Иммермана – Селепсеньи .

В частности, проблема st-связности на самом деле является NL-полной , то есть каждая проблема в классе NL сводится к связности при уменьшении лог-пространства . Это остается верным для более сильного случая редукций первого порядка ( Immerman 1999 , p. 51). Сокращение пространства журнала с любого языка в NL до STCON происходит следующим образом: Рассмотрим недетерминированную машину Тьюринга M в пространстве журнала, которая принимает язык в NL. Поскольку на рабочей ленте есть только логарифмическое пространство, все возможные состояния машины Тьюринга (где состояние - это состояние внутреннего конечного автомата, положение головы и содержимое рабочей ленты) полиномиально много. Сопоставьте все возможные состояния детерминированной машины лог-пространства с вершинами графа и поместите ребро между u и v, если состояние v может быть достигнуто из u в пределах одного шага недетерминированной машины. Теперь проблема того, принимает ли машина, такая же, как проблема того, существует ли путь от начального состояния к принимающему состоянию.

Теорема Сэвича гарантирует, что алгоритм может быть смоделирован в детерминированном пространстве O (log ²  n ).

Та же проблема для неориентированных графов называется неориентированной связностью и была L- завершена Омером Рейнгольдом . Это исследование принесло ему в 2005 году премию Грейс Мюррей Хоппер . Ранее было известно, что неориентированная st-связность является полной для класса SL , поэтому работа Рейнгольда показала, что SL является тем же классом, что и L. На чередующихся графах проблема P -полна ( Immerman 1999 , p. 54).

Ссылки

• Сипсер, Майкл (2006), Введение в теорию вычислений , Технология курса Томпсона, ISBN 0-534-95097-3
• Иммерман, Нил (1999), описательная сложность , Нью-Йорк: Springer-Verlag, ISBN 0-387-98600-6