st-связность

В информатике st-связность или STCON — это задача принятия решения , в которой для вершин s и t в ориентированном графе спрашивается , достижима ли t из s .

Формально задача решения задается как

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

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

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

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

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

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

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