Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В информатике задача связности st или STCON — это задача принятия решения, которая для заданных вершин s и t в ориентированном графе определяет, достижима ли вершина t из вершины s.
In computer science, st connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s.
Формально, задача принятия решения задается следующим образом:
Formally, the decision problem is given by
.
Сложность
На последовательном компьютере задача проверки связности между вершинами s и t (st-связность) может быть легко решена за линейное время с помощью поиска в глубину или поиска в ширину. Интерес к этой задаче в вычислительной сложности связан с её сложностью при использовании более ограниченных моделей вычислений. Например, класс сложности задач, которые могут быть решены недетерминированной машиной Тьюринга, используя лишь логарифмический объём памяти, называется NL. Можно показать, что задача st-связности принадлежит классу NL, поскольку недетерминированная машина Тьюринга может угадывать следующую вершину пути, при этом необходимо хранить только общую длину пути и текущую рассматриваемую вершину. Алгоритм завершается, если достигнута целевая вершина t или длина текущего пути превышает n – количество вершин в графе. Дополнение к задаче st-связности, известное как st-несвязность, также принадлежит классу NL, поскольку NL = coNL согласно теореме Иммермана — Селепчени. В частности, задача st-связности является NL-полной, то есть любая задача из класса NL приводима к задаче st-связности посредством логарифмического сжатия. Это справедливо и для более сильного случая приведения первого порядка. Логарифмическое сжатие из любого языка в NL к STCON выполняется следующим образом: рассмотрим недетерминированную машину Тьюринга M с логарифмическим объёмом рабочей памяти, принимающую язык из NL. Поскольку на рабочей ленте доступно лишь логарифмическое пространство, количество всех возможных состояний машины Тьюринга (где состояние определяется состоянием конечного автомата, положением головки и содержимым рабочей ленты) является полиномиальным. Отобразим все возможные состояния детерминированной машины с логарифмическим объёмом памяти на вершины графа и проведём ребро между u и v, если состояние v достижимо из u за один шаг недетерминированной машины. Теперь задача определения, принимает ли машина, эквивалентна задаче поиска пути от начального состояния к принимающему состоянию. Теорема Савича гарантирует, что алгоритм может быть смоделирован в O(log² n) детерминированного пространства. Та же задача для неориентированных графов называется неориентированной st-связностью и была показана принадлежащей классу L Омером Рейнгольдом. Это исследование принесло ему премию Грейс Мюррей Хоппер в 2005 году. Ранее было известно, что неориентированная st-связность является полной для класса SL, поэтому работа Рейнгольда показала, что SL и L – это один и тот же класс. Для чередующихся графов задача является P-полной.
On a sequential computer, st connectivity can easily be solved in linear time by either depth first search or breadth first search. The interest in this problem in computational complexity concerns its complexity with respect to more limited forms of computation. For instance, the complexity class of problems that can be solved by a non deterministic Turing machine using only a logarithmic amount of memory is called NL. The st connectivity problem can be shown to be in NL, as a non deterministic Turing machine can guess the next node of the path, while the only information which has to be stored is the total length of the path and which node is currently under consideration. The algorithm terminates if either the target node t is reached, or the length of the path so far exceeds n, the number of nodes in the graph. The complement of st connectivity, known as st non connectivity, is also in the class NL, since NL = coNL by the Immerman–Szelepcsényi theorem. In particular, the problem of st connectivity is actually NL complete, that is, every problem in the class NL is reducible to connectivity under a log space reduction. This remains true for the stronger case of first order reductions The log space reduction from any language in NL to STCON proceeds as follows: Consider the non deterministic log space Turing machine M that accepts a language in NL. Since there is only logarithmic space on the work tape, all possible states of the Turing machine (where a state is the state of the internal finite state machine, the position of the head and the contents of the work tape) are polynomially many. Map all possible states of the deterministic log space machine to vertices of a graph, and put an edge between u and v if the state v can be reached from u within one step of the non deterministic machine. Now the problem of whether the machine accepts is the same as the problem of whether there exists a path from the start state to the accepting state. Savitch's theorem guarantees that the algorithm can be simulated in O(log2 n) deterministic space. The same problem for undirected graphs is called undirected s t connectivity and was shown to be in L by Omer Reingold. This research won him the 2005 Grace Murray Hopper Award. Undirected st connectivity was previously known to be complete for the class SL, so Reingold's work showed that SL is the same class as L. On alternating graphs, the problem is P complete .