Изменения

Даны ориентированный граф <tex> G = \langle V, E \rangle </tex> и две вершины <tex> s, t</tex> в нем. Необходимо проверить, правда ли, что в графе <tex> G </tex> существует путь из вершины <tex> s </tex> в вершину <tex> t </tex>. Эту задачу принято называть <tex> REACH st-connectivity </tex> или <tex> STCON </tex>.

Задача <tex> REACH STCON </tex> [[NL-полнота|NL-полна]]. == Доказательство ==Для доказательства [[NL-полнота|NL-полноты]] необходимо показать, что эта задача NL-трудная и принадлежит [[NL|классу NL]]. === Доказательство принадлежности задачи STCON классу NL === === Доказательство NL-трудности задачи STCON ===