В информатике , ули связность или ЭСТЕКОН является проблема решения запрашиваемой для вершины 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 2 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