st-связность

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

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

ПУТЬ знак равно {⟨ D, s, т ⟩ | 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 ) детерминированное пространство.

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

Ссылки

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